[BOJ] Moo 게임 5904 C++ 풀이 [분할정복]

문제

Moo는 술자리에서 즐겁게 할 수 있는 게임이다. 이 게임은 Moo수열을 각 사람이 하나씩 순서대로 외치면 되는 게임이다.

Moo 수열은 길이가 무한대이며, 다음과 같이 생겼다.

m o o m o o o m o o m o o o o m o o m o o o m o o m o o o o o 

Moo 수열은 다음과 같은 방법으로 재귀적으로 만들 수 있다. 먼저, S(0)을 길이가 3인 수열 “m o o”이라고 하자. 1보다 크거나 같은 모든 k에 대해서, S(k)는 S(k-1)과 o가 k+2개인 수열 “m o … o” 와 S(k-1)을 합쳐서 만들 수 있다.

S(0) = "m o o"
S(1) = "m o o m o o o m o o"
S(2) = "m o o m o o o m o o m o o o o m o o m o o o m o o"

위와 같은 식으로 만들면, 길이가 무한대인 문자열을 만들 수 있으며, 그 수열을 Moo 수열이라고 한다.

N이 주어졌을 때, Moo 수열의 N번째 글자를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (1 ≤ N ≤ 10^9)이 주어진다.

출력

N번째 글자를 출력한다.

접근방법

일정한 패턴으로 반복되는 Moo 문자열을 보며 하나의 긴 Moo 문자열을 작은 단위로 쪼개어 나아갔을때 N번째 글자에 해당하는 문자를 찾을 수 있을 것이라 생각하였다.

예제의 S$($2) m o o m o o o m o o m o o o o m o o m o o o m o o 에서 n=5인 경우를 보면

S$($2) 문자열은 총 세개의 구간으로 나눌 수 있다. S$($1) + $($m o o o + o) + S$($1)

이때 5번째 문자는 세개의 구간 중 앞의 S$($1)에 속하여 있으므로 앞부분만을 때어내어 이번에는 S$($1)을 다시 세 등분해서 진행한다.

` m o o m o o o ` m o o

여기서 5번째 문자는 중간 구간에 속해있으므로 이 경우에는 n - 앞의 S(0)문자열의 길이의 값이 1인 경우 m을 출력하고 아닌경우 o를 출력하며 반복문을 탈출하면 된다.

찾고자 하는 문자가 세 구간의 제일 뒷부분에 존재하는 경우에는 앞의 두 구간의 경우와 달리 n의 값도 같이 갱신해 줘야 한다. n -= prev + mid;

구현

#include<iostream>
using namespace std;

int main(void)
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n;
    int mid;
    int total_len, prev;
    total_len = prev = mid = 3;

    cin>>n;
    while(n > total_len)
    {
        int tmp = (total_len * 2) + ++mid;
        total_len = tmp;
    }

    while(true)
    {
        prev = (total_len - mid) / 2;
        if(n <= prev)
        {
            total_len = prev;
            mid--;
            continue;
        }

        if(n > prev+mid)
        {
            total_len = prev;
            n -= prev + mid;
            mid--;
            continue;
        }

        n -= prev;
        break;
    }

    if(n == 1) cout<<'m';
    else cout<<'o';

    return 0;
}

오답노트

세 구간 중에서 찾고자 하는 문자가 뒷 구간에 있는 경우 n값을 갱신해 줘야 한다는 것을 인지하지 못하여 시간초과가 발생하였다.