[백준 5904 - C++] Moo 게임 : 분할 정복

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

5904번: Moo 게임

문제

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번째 글자를 출력한다.

 

예제 입력 1 

11

예제 출력 1 

m

 

 

반응형

 

풀이

일단 이 문제에서 Moo수열을 저장해서 풀 생각은 절대로 해서는 안된다.

N의 최대값이 10^9이기 때문에 저장을 하려고 해도 아마 불가능할 것이다.

 

따라서 이문제에서는 저 수열의 길이를 이용해야한다.

len(S(k) = len(S(k-1))*2 + k1 + 3

라는 점화식은 쉽게 생각할 수 있다. 이제 이를 이용할 수 있도록 재귀를 짜는 것이 중요하다.

 

우선 만약 N이 3이하라면 그냥 "moo"에 따른 값을 출력한다.

 

Moo수열의 S(k)는 S(k-1) mo...oS(k-1)로 이루어진다.이를 잘 이용해야한다.

우선 len*2+k+3이 N보다 커질때까지 재귀를 반복한다.

커진 경우 N은 절대로 1~len사이의 숫자일 수는 없다.

따라서 len~len+k+3 사이의 수인지를 확인하고 그 사이의 수라면 len+1인 경우엔 "m"을 나머지 경우엔 "o"을 출력하고 종료한다.

그 사이의 수가 아니라면 N은 뒤쪽의 S(k-1)에 위치하는 것이다.

따라서 S(k-1)중 어느 위치인지 찾기 위해 또 재귀호출을 한다.

이때 중요한 것은 n=n-(len+k+3)이 된 채로 재귀가 실행되어야 한다는 것이다. 물론 k=1이되고 len = 3이 되게 다시 재귀를 처음부터 시작하는 것이다.

 

사실 제출하면서 시간초과가 날 수도 있지 않나..?라고 생각했는데 아무 문제없었다. 휴!

 

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

char s1[3] = {'m', 'o','o'};

void sol(int n, int k, int len){
    int new_len = len*2 + k+3;
    if(n<=3){
        printf("%c\n", s1[n-1]);
        exit(0);
    }
    if(new_len < n){
        sol(n, k+1, new_len);
    }
    else{
        if(n > len && n <= len+k+3){
            if(n-len != 1)
                printf("o\n");
            else
                printf("m\n");
            exit(0);
        }
        else{
            sol(n-(len+k+3), 1, 3);
        }
    }
}

int main(void){
    int n;
   
    scanf("%d", &n);
    
    sol(n, 1, 3);
    
}