이번 문제는 분할정복으로 해결하였다. 처음에는 재귀방식으로 Moo배열을 만들어 주려고 생각을 했었다. 그러나 구현하던 도중에 n의 범위가 10억이기 때문에 메모리 초과가 발생한다는 사실을 알게 되었다.

그래서 Moo배열의 길이를 이용하여 길이가 n보다 크거나 같을 때까지 Moo 배열의 길이를 증가 시킨 뒤에 s(k-1), m+o*(k+2), s(k-1) 중에 어디에 속하는지 확인한 뒤에 그 범위 내에서 글자를 구하였다.

• Moo배열의 길이의 증가에 대한 패턴을 보면 len(2*s(k-1))+(1+k+2)이다. 변수 len에 s(k-1)의 길이를 저장하여 재귀함수의 매 반복마다 Moo배열의 길이를 늘린다.
• n이 3이하라면 moo안에서 해결이 가능하다.
• 새로운 Moo배열의 길이 nlen이 n보다 크거나 같다면 n번째 문자를 구할 수 있다. 이때 n이 기존의 Moo배열의 길이보다 크고, 기존의 Moo배열의 길이+k+3보다 작을 때 (m+o*(k+2)범위일 때) n-기존의 길이가 1이 아니면 o를, 1이라면 m을 출력하도록 한다. n이 m+o*(k+2)범위 외일 때는 범위를 s(k-1)로 줄여 재귀함수를 호출하여 탐색한다.
• 새로운 Moo배열 nlen이 n보다 작다면 Moo배열이 더 길어져야 하므로 재귀함수를 호출하여 길이를 증가시킨다.

Code

#include <iostream>
using namespace std;

long long n;
char s[3]={'m','o','o'};

void Input(){
    cin>>n;
}

void Solution(long long n1, long long k, long long len){
    long long nlen=len*2+k+3;
    if(n1<=3){
        cout<<s[n1-1]<<endl;
        exit(0);
    }
    if(nlen>=n1){
        if(n1>len&&n1<=len+k+3){
            if(n1-len!=1){
                cout<<"o"<<endl;
                exit(0);
            }
            else{
                cout<<"m"<<endl;
                exit(0);
            }
        }
        else{
            Solution(n1-(len+k+3), 1, 3);
        }
    }
    else{
        Solution(n1, k+1, nlen);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    Solution(n,1,3);
    return 0;
}