[백준/BOJ] 8892번 : 팰린드롬, 9656번 : 돌 게임 2, 1292번 : 쉽게 푸는 문제

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 8892번 : '팰린드롬', 9656번 : '돌 게임 2', 1292번 : '쉽게 푸는 문제' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Silver 티어에 해당하며, 랜덤으로 문제를 풀이하고 있기에 알고리즘 분류는 다양하게 나올 수 있습니다.

 

 

8892번 : 팰린드롬

 

주어진 k개의 문자열 중에서 2개를 조합하여 팰린드롬 문자열을 만들 수 있다면 해당 문자열을 출력하고, 그러한 조합이 단 한 가지 경우도 없다면 0을 출력하는 문제입니다.

 

문제 티어가 Silver V에 해당하고, 알고리즘의 분류가 브루트포스 알고리즘으로 되어있기 때문에 모든 경우의 수를 조합해서 확인해 볼 수 있습니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int T; cin >> T;

    while(T--) {
        int N; cin >> N;

        vector<string> str(N);
        for(int i=0; i<N; i++) cin >> str[i];

        bool foundAns = false;
        for(int i=0; i<N; i++) {
            for(int j=i+1; j<N; j++) {
                for(int k=0; k<2; k++) {
                    string temp;
                    if(k == 0) temp = str[i] + str[j];
                    else temp = str[j] + str[i];

                    bool check = true;
                    for(int l=0; l<temp.length()/2; l++)
                        if(temp[l] != temp[temp.length()-1-l]) {
                            check = false;
                            break;
                        }

                    if(check) {
                        cout << temp << "\n";
                        foundAns = true;
                        break;
                    }
                }
                if(foundAns) break;
            }
            if(foundAns) break;
        }

        if(!foundAns) cout << "0\n";
    }
}

 

다만 이 문제의 경우 풀이 코드가 살짝 길어지는데, 그 이유는 우선 두 문자열을 순서를 다르게 하여 조합을 할 수 있기 때문이고, 각 조합에 대해 검사가 필요하며, 만약 팰린드롬 문자열을 찾은 경우에는 모든 반복문을 종료해주어야 하기 때문입니다.

 

그래서 foundAns라는 bool 변수를 두고 답을 찾은 경우 출력 후 foundAns = true로 바꾸어 모든 반복문을 종료하도록 설정해주었습니다.

 

 

 

 

9656번 : 돌 게임 2

 

돌 N개를 1개 또는 3개씩 번갈아가며 가져간다고 하고, 마지막 돌을 가져가는 사람이 진다고 할 때 이기는 사람을 구하는 문제입니다.

 

잘 생각해보면 돌은 무조건 홀수개만 가져갈 수 있으므로 N의 홀짝성에 따라 두 사람이 어떤 선택을 해도 승패는 고정되게 됩니다.

N = 4일 때 SK가 승자이므로 짝수일 때는 SK, 홀수일 때는 CY를 출력해주면 됩니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    if(N%2 == 0) cout << "SK";
    else cout << "CY";
}

 

풀이 코드는 위와 같이 아주 간단함을 확인할 수 있습니다.

 

 

 

 

1292번 : 쉽게 푸는 문제

 

1이 한 번, 2가 두 번, 3이 세 번, ... 으로 이루어진 수열이 있을 때 A번째 수부터 B번째 수까지 합한 값을 구하는 문제입니다.

Silver V 티어 문제이므로 배열에 그냥 값을 저장하고 A부터 B번째 수까지 다 더해주는 방식으로 구현해도 됩니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int A, B; cin >> A >> B;

    int arr[1001], cnt = 1;
    for(int i=1, j=1; i<=B; i++, j++) {
        arr[i] = cnt;
        if(j == cnt) j = 0, cnt++;
    }

    int sum = 0;
    for(int i=A; i<=B; i++) sum += arr[i];

    cout << sum;
}

 

위와 같이 cnt라는 상한선을 정하고, j를 0부터 계속 증가시켜주면서 cnt에 도달할때마다 j를 0으로 되돌려주면면서 cnt 값을 arr에 값을 저장해주었습니다.

그 뒤에 A번째부터 B번째 arr 값을 더해서 sum에 합쳐준 뒤 출력해주면 됩니다.