[백준 5904] Moo 게임

5904번: Moo 게임

알고리즘 : 재귀

난이도 : 골드Ⅴ

 

1. 문제요약

• moo 수열은 길이가 무한대인 수열로, 다음과 같은 과정으로 만들어진다.
  • 일단 moo로 시작한다. m과 o 두개가 붙어있다.
  • 두개의 moo사이에 o가 하나 더붙은 mooo가 삽입되어 moomooomoo가 된다.
  • 두개의 moomooomoo 사이에 o가 하나 더붙은 moooo가 삽입되어 moomooomoomoooomoomooomoo가 된다.
  • 위 과정을 계속 반복하면 길이가 무한대인 moo수열이 된다.
• $10^9$이하의 숫자 n이 주어질때, moo수열의 n번째 글자를 출력한다.

2. 아이디어

• moo수열은 길이가 무한대이지만, 당연하게도 주어진 숫자 n을 커버할정도의 길이만 생각하면 된다.
• moo수열이 만들어지는 과정을 단계별로 나누어 생각하자. S(x)는 x번째 단계에서 만들어지는 moo수열이라고 하자.
• 우선 S(x) = S(x-1) + moo ... o + S(x-1)임을 쉽게 알 수 있다. 여기서 중간의 o는 x+1개 들어간다.
• 위 수식으로부터 S(x)의 길이를 알 수 있다. S(1) = 3이고 S(x)의 길이는 S(x-1)의 길이의 두배에 x+2만큼 더한 값이 된다는 점으로부터 S(x)의 길이 $2^{x+2} - (x+4)$임을 얻게 된다.
• 수열 S(x)의 n번째 문자를 구하는 함수 f(x,n)을 생각해보자. n번째 문자는 1) S(x)에서 왼쪽 부분의 수열 S(x-1)에 존재할 수 도 있고, 2) 중간의 수열 moo ... o에 존재할 수 도 있고, 3) 오른쪽 부분의 수열 S(x-1)에 존재할 수 도 있다.
• 1)의 경우에는 $f(x,n) = f(x-1,n)$이 됨을 쉽게 알 수 있다.
• 2)의 경우는 n이 $2^{x+1}-(x+3)$보다 크고 $2^{x+1}$보다 작은 경우로서, $n=2^{x+1}-(x+2)$인 경우 m, 이외의 경우에는 o임을 알 수 있다.
• 3)의 경우는 1)에서와 마찬가지인데, $f(x,n) = f(x-1,n-(2^{x+1}-1))$이 됨을 알 수 있다.

3. 구현과정

• 함수 f(x,n)부터 정의한다. 우선 x = 1인 경우 수열은 moo이므로 n = 1일때 m, 이외에는 o를 반환하면 된다.
• x = 1이 아닌 경우, 즉 x가 1보다 큰 경우에는 위에서 생각해낸 수식을 따라 재귀함수를 만들면 된다.
• 함수 f(x,n)에서 인자 n은 입력으로 받게되지만 인자 x는 직접 구해야 한다. while문을 활용하여 n보다 작은 $2^{x+2}-(x+4)$중 가장 큰 x를 구해서 함수에 넣어주면 될 것이다.

4. 파이썬 코드

# x단계의 moo수열에서 n번째 글자를 구하는 함수
def f(x, n):
    if x == 1:
        return 'm' if n == 1 else 'o'
    else:  # x > 1일때
        # n번째 위치가 수열의 중간부분인 경우
        if 2 ** (x + 1) - (x + 3) < n < 2 ** (x + 1):
            return 'm' if n == 2 ** (x + 1) - (x + 2) else 'o'
        # n번째 위치가 수열의 왼쪽 또는 오른쪽인 경우
        else:
            if n >= 2 ** (x + 1): # 수열의 오른쪽인 경우에 해당함
                n -= 2 ** (x + 1) - 1
            return f(x - 1, n)

N = int(input())
X = 3
while 2 ** (X + 2) - (X + 4) < N:
    X += 1
print(f(X, N))