5904(Moo 게임) - 해결

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 ≤ 109)이 주어진다.

 

출력

N번째 글자를 출력한다.

---

역시 단순히 풀면 메모리 초과가 나온다.

분할을 해서 앞의 S(k - 1) 부분과 m o * (k + 2)와 뒤의 S(k - 1)을 구분하여 어디에 속하는 지 파악을 하였다.

그전에 먼저 어떤 k 의 S(k)에 속하는지 파악하려고 하였다.

그 후에 분할을 하면서 어디에 속하는 지 파악하였다.

import sys
input = sys.stdin.readline

N = int(input())

# S(k) 저장
S = [3]
k = 0
# 인덱스로 찾기 위해 -1을 해주었다
N -= 1

# 어떤 S(k)에 속하는 지 찾기
while S[k] <= N:
    k += 1
    S.append(S[k-1] * 2 + (k + 2) + 1)

# k를 줄여가며 분할하면서 어디에 속하는 지 파악
while k > 0:
    # 앞의 S(k-1)에 속하면 k만 줄인다
    if N < S[k-1]:
        pass
    # 뒤의 S(k-1)에 속하면 앞의 길이 만큼 인덱스를 줄이고
    # 그안에서 찾는다.
    elif N >= S[k-1] + (k + 2) + 1:
        N -= S[k-1] + (k + 2) + 1
    # m + o * (k + 1)에 속하면 바로 나온다.
    else:
        N -= S[k-1]
        break
    k -= 1

# 여기에 오는거면 S(0) 즉, 'moo'나 m + o * (k + 1)에 속한다.
# 그렇기 때문에 처음이 아니면 o 처음이면 m
if N == 0:
    print('m')
else:
    print('o')