[백준] C++ 5904: Moo 게임 - 굉장히 큰 수에 대한 재귀

https://www.acmicpc.net/problem/5904

---

N이 10^9 개로 N번째 글자를 구한다는 것이 몇 번째 수열을 구해야 하는지 감도 안잡히고 굉장히 큰 수여서 long long으로도 담지 못한다.

즉, 재귀적으로 길이가 n 이상인 수열을 구해서 n번째 문자를  찾으려 한다면 절대 풀 수 없다.

조금 다르게 생각해서 n번째 글자만 알면 되므로 어떤 수열에 대해 n번째 글자를 알아내는 과정을 재귀로 생각하여야 한다.

 

사실 다 풀고 나서야 이렇게 명료하게 말할 수 있지만 풀 때는 다음과 같은 과정을 거쳤다.

1. 수열의 길이가 n 이상인 moo 수열 구하기 -> 구현을 다 하고 보니 n이 얼마 이상 커지면 오류
2. k번째 moo 수열 S(k)에 대해 S(k-1)의 길이를 알면 S(k)를 알 수 있음. 그럼 길이를 가지고 뭘 할 수 있을까?
   1. S(k) 수열은 S(k-1), k-2, S(k-1) 이렇게 a b c 형태로 구성되어 있음.
   2. 길이를 안다면 n번째 문자가 저 세 가지 섹션 중 어디에 속해있는지 알 수 있음.
   3. 어느 섹션에 속해있는지 안다면 다음과 같이 처리할 수 있음.
      1. S(k-1) -> 그 안에서 또 어디 섹션에 속해있는지 판단.
      2. k-2 -> m인지 o인지 찾으면 끝!

마지막 두 조건을 보면서 아 이거 k-2에 속하면 base condition 그렇지 않으면 재귀식을 호출하는 재귀구나! 해서 구현했다.

/** 재귀 5904 Moo 게임 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int n;
long long len[1000];
// n이 10^9으로 n번째 수열을 구하는 것은 불가능함.
// n번째 문자가 무엇인지를 구하는 것이 가장 핵심
// S(k-1)의 길이를 안다면 n번째 문자가 무엇인지 알 수 있음!
// S(k-1)의 길이를 l이라 한다면 S(k)의 0~l-1 까지의 수열은 S(k-1), l ~ l+k+3 까지는 moooo..o, 그 뒤부터는 S(k-1)

// n번째 문자가 S(k-1)에 속했다면 S(k-1)에서 어디에 속했는지 구하기
// n번째 문자가 mo...o에 속했다면 바로 구하기

char solve(int k, long long n)
{
    // base condition
    if (k == 0)
        if (n == 0)
            return 'm';
        else
            return 'o';

    // 재귀식
    if (n < len[k - 1])
    {
        // n이 S(n-1)에 속함
        return solve(k - 1, n);
    }
    else if (n < len[k - 1] + k + 3)
    {
        // n이 가운데에 속함
        if (n == len[k - 1])
            return 'm';
        return 'o';
    }
    else
    {
        // n이 마지막 S(n-1)에 속함
        // 마지막에 속해있다는 것은 그 n을 앞으로 땡겨서 제일 처음에 속한것과 똑같이 처리할 수 있음
        return solve(k - 1, n - (len[k - 1] + k + 3));
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    n--; // 0 based index
    len[0] = 3;
    int k = 0;
    while (len[k] <= n)
    {
        k++;
        len[k] = len[k - 1] * 2 + k + 3;
    }

    cout << solve(k, n) << '\n';
}