[WEEK02] 정글시험 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 ≤ 109)이 주어진다.

출력

N번째 글자를 출력한다.

풀이

분할정복 문제이다. Len(n) = Len(n - 1) + K + Len(n - 1) 이렇게 표현할 수 있다.
따라서 좌측, 우측, 중앙 으로 분리하였다.

먼저, 입력받은 N을 포함할 수 있는 배열의 길이와 K값에 해당하는 값을 구해준다.
이 값을 인자로 받고 영역을 분리해준다.

전체 길이가 L 이라 하면 좌측, 우측 각각의 길이는 (L - K) // 2가 될것이다.

전체코드

def func(length, mid_cnt, target_idx):
    prev_cnt = (length - mid_cnt) // 2

    # 좌측영역에 속하는 인덱스면 좌측영역으로
    if target_idx < prev_cnt: 
        return func(prev_cnt, mid_cnt - 1, target_idx)
    # 우측영역에 속하는 인덱스면 우측영역으로
    elif target_idx >= prev_cnt + mid_cnt: 
        return func(prev_cnt, mid_cnt - 1, target_idx - (prev_cnt + mid_cnt))
    # 가운데영역이면 바로 출력
    # m 1개와 o로만 이루어져있음
    else:
        return 'o' if target_idx - prev_cnt else 'm'

n = int(input())
length = 3
k = 3

# n번째를 포함할 수 있는 배열의 길이와 mid 길이 얻는과정
while True:
    if length >= n:
        break
    k += 1
    length = 2 * length + k

# 몇 번째 글자를 원하니 인덱스는 -1 해주면 됨
print(func(length, k, n - 1))