[Python/파이썬] 백준 5904번 Moo 게임

5904번: Moo 게임

 

코드

n = int(input())


def dc(k, l, n):    # K, S(K)의 길이, 구하는 순서 N
    if n <= 3:
        return ("m" if n == 1 else "o")
    center = k+3
    left = (l-center)//2
    if n <= left:
        return dc(k-1, left, n)
    elif n > (left+center):
        return dc(k-1, left, n-(left+center))
    else:
        return ("m" if left+1 == n else "o")


# n이 포함된 Moo 수열이 몇번째인지
l = 3
k = 1
while True:
    l = 2*l+k+3
    if l > n:
        break
    k += 1

print(dc(k, l, n))

 

분할정복을 이용하여 Moo 수열의 N번째 문자를 구한다.

 

큰 수열에서 작은 수열로 분할하는 방식을 쓸 것이므로 n이 포함되는 가장 최소의 S(k)수열을 먼저 구한다. 

S(k)의 길이 = S(k-1)의 길이+k+3이므로 이걸 이용하면 n이 포함되는 가장 최소의 S(k)일 때의 k와 그때의 길이 l을 구할 수 있다. 이 값으로 dc(k, l, n)을 수행한다.

 

dc(k, l, n)

S(k)를 세 부분으로 자르면 왼쪽은 S(k-1), 가운데 k+3만큼의 길이는 "m"+'o"×(k+2), 오른쪽은 S(k-1)이다. 가운데의 길이가 k+3이라면 양쪽 옆부분은 전체에서 가운데를 빼고 2로 나눈 값이다. 만약 n이 왼쪽에 포함되어 있다면 재귀적으로 dc(k-1, left, n)을 수행하여 왼쪽 부분을 계속하여 탐색하고 오른쪽이라면 n에서 왼쪽과 가운데를 합친 값을 빼주어 왼쪽을 탐색할 때와 같게 해준다. 그리고 만약 가운데 부분이라면 가장 앞글자만 "m"이고 나머지는 모두 "o"이므로 맞는 값을 리턴한다.