BOJ 5904 : Moo 게임

풀이 요약

분할 정복

풀이 상세

1. 문제가 원하는 것은 결국 $N$ 번째의 글자가 어떤 글자인지 구하는 것이다. 예를 들어 S(2) 인 경우를 살펴보면 글자는 총 3가지로 분류가 된다.
   • “moo / mooo / moo”
   • 첫번째 : 이전의 길이. $S(N-1)$;
   • 두번째 : 현재 새롭게 추가되는 값. $K+3$;
   • 세번째 : 이전의 길이. $S(N-1)$;
2. 즉 다음 길이로 추가되는 총 길이의 값은 $2*prevLen + K+3$ 이 된다.
3. 만약 다음 길이가 $N$ 보다 부족하다면 다시 다음길이를 구하기 위해 $K$ 값을 높여준다.
4. 아니라면 두번째에 포함되는지 아닌지를 분류하여, 만약 $N$ 이 글자의 두번째 분류에 속한 경우, 이전의 길이 만큼 뺏을 때 인덱스가 0 이라면 ‘m’ 그렇지 않은 경우는 모두 ‘o’ 가 된다.
5. 두번째에 포함이 되지 않은 경우라면, 두번째 분류와 세번째 분류를 빼가면서, 최소 단위인 “moo” 까지 돌아가, 그 때 가지고 있는 $N$ 의 값이 몇번째에 있는지 확인한다.

배운점

• 이전의 상태를 저장하며 하는 방식으로 구할까 했는데, 메모리 초과가 나왔다. 아무래도 최대 $10^9$ 이기 때문에 벡터에 모두 저장하며 나아가기에는 메모리가 부족했나보다.

#include <iostream>
using namespace std;

void solve(int N, int next_idx, int curr_len) {
    int next_len = curr_len * 2 + next_idx + 3;
    if (N <= 3) {
        cout << (N - 1 == 0 ? 'm' : 'o');
        return;
    }
    if (next_len < N) {
        solve(N, next_idx + 1, next_len);
    } else {
        if (N > curr_len && N <= curr_len + next_idx + 3) {
            cout << (N - curr_len - 1 == 0 ? 'm' : 'o');
            return;
        } else {
            solve(N - (curr_len + next_idx + 3), 1, 3);
        }
    }
}

int main() {
    int num;
    cin >> num;
    solve(num, 1, 3);
}