[WEEK 03] 백준 5094번 - Moo 게임 (Python)

백준 5094번 Moo 게임

 

 

문제에서 정의된 Moo 수열의 N번째 글자를 구하는 문제다. 해당 문제를 접했을 때, 아래처럼 Moo 수열 자체를 구하다보니 메모리 초과가 발생하였다.

 

def moo(k) :

    if k == 0 :
        return "moo"

    tmp = "m" + "o" * (k + 2)

    return moo(k-1) + tmp + moo(k-1)

 

문제 조건에서 Moo 수열의 길이는 '무한대'라고 했기 때문에 수열 자체를 출력할 수 없다고 생각했다. 또한, \(1 \leq N \leq 10^{9}\) 인 것을 고려했을 때 다른 방법으로 풀이하도록 유도하는 것 같았다.

 

 

Moo 수열은 아래와 같이 나타낼 수 있다.

 

moo(n) = moo(n-1) + "m" + "o" * (n+2) + moo(n-1)

 

이처럼 세 개의 항으로 나눌 수 있으며, 가운데 항의 경우 문자열의 개수를 알고 있다. moo(n-1) 항의 문자열 개수는 전체 문자열 개수에서 가운데 항의 문자열 개수를 빼고 2로 나누어주면 되고, 이는 재귀 호출을 이용한 분할 정복으로 최종적으로 구할 수 있다.

 

 

문자열의 '개수'에 초점을 맞추어 해당 문제를 접근하기 위해서는 어떠한 사고가 필요한지 생각해보았다. 

 

 

먼저, 수열을 구성하고 있는 식이 세 개의 항으로 나누어져 있으므로, n이 어디에 위치하느냐를 분기로 나누어 연산 과정을 간소화시킬 수 있다고 생각한다. 각 항들의 문자열 개수를 파악할 수 있으므로, case마다 n이 몇번째에 해당하는지 계산할 수 있다.

 

 

n이 주어질때, n보다 크거나 같은 최소 길이의 Moo 수열을 만들기 때문에 공간 복잡도의 측면에서 유리하다고 생각한다. Moo 수열은 S(1), S(2), ... 반복 시행을 통해 규칙을 찾을 수 있고 이를 점화식으로 나타낼 수 있다.

 

import sys

sys.stdin = open('input.txt', 'r')

n = int(sys.stdin.readline())

def moo(tot, mid, k) :
    front = (tot - mid) // 2

    if k <= front :
        return moo(front, mid - 1, k)

    elif k > front + mid :
        return moo(front, mid - 1, k - front - mid)

    else :
        if k == front + 1 :
            return "m"

        else :
            return "o"

tot, i = 3, 0

while n > tot :
    i += 1
    tot = tot * 2 + (i + 3)

print(moo(tot, i + 3, n))