[복기] 5904번: Moo 게임

문제

[백준 5904번: Moo 게임]

나의 풀이: 단순 수열 구현(메모리 초과)

수열 문제이므로 보자마자 수열 문자열을 직접 생성하는 코드를 짜버렸다. 당연히 메모리가 터진다. 골드 5의 문제가 그렇게 단순할리가 없다. 그런데도 터질걸 알면서도 구현해버렸다.

단순 수열

n = int(input())

s = "moo"
def moo(k):
    global s
    if k == 0:
        return s
    s = s + 'm'+('o'*(k+2)) + s

k = 0
while True:
    if len(s) >= n:
        print(s[n-1])
        break
    else:
        k += 1
        moo(k)

나의 풀이: 분할정복(성공)

아무튼 골드 5답게 시간 제한과 메모리 제한이 있기 때문에, 다른 방법을 써야 한다. 나는 분할정복을 적용했다. Moo 수열은 재귀적인 형태를 띄고있으므로, 왼쪽 수열과 오른쪽 수열, 그리고 중간 수열로 나누어서 정복하면 된다. 각 수열의 구간을 지정하기 위해 수열의 길이를 알 필요가 있다.

수열 점화식: S(N) == S(N-1) + "M" + "O" * (N+2) + S(N-1)

수열의 길이 점화식: a(n) == 2 * a(n-1) + n + 4

Moo 수열의 점화식은 위와 같다. 보다시피 위 점화식을 일반항을 구하는 것은 무척 어렵다. 애초에 코딩테스트는 수학을 엄청 요구하는 시험이 아니기 때문에 점화식을 구해서 푸는 문제는 아닐 것이다. 하지만 수열의 길이는 구할 수 있다. 분할정복을 하기 전에 미리 수열의 길이를 구한다. dp[i]가 수열 S(i)의 길이를 저장하고 있다.

length = 3
idx = 0
dp = [3]
while True:
    length = 2*length + idx + 4
    dp.append(length)
    idx += 1
    if length > n:
        break

이제 구해야할 N번째 인덱스가 속할 구간을 찾는다. N이 왼쪽 수열에 있을지, 오른쪽 수열에 있을지, 중간 수열에 있을지를 조건문으로 찾는다. 찾았으면 범위를 좁히고 재귀호출한다. 충분히 좁혀졌으면 n번째 문자를 리턴한다.

def solution(left, idx, n):
    if idx < -1:
        return s[n]
        
    if n < dp[idx]: ## 왼쪽 수열에 있는 경우
        return solution(left, idx-1, n)
    elif n >= idx+4 + dp[idx]: ## 오른쪽 수열에 있는 경우
        return solution(left, idx-1, n-(idx+4+dp[idx]))
    else: ## 중간 수열에 있는 경우
        if n - dp[idx] == 0: ## 중간 수열은 첫 글자만 'm'
            return 'm'
        else:
            return 'o'

중간 수열은 'mooooooo...'처럼 첫 글자만 'm'이기 때문에 첫글자인지만 확인해주면 된다.

전체 코드

n = int(input())

s = "moo"
length = 3
idx = 0
dp = [3]
while True:
    length = 2*length + idx + 4
    dp.append(length)
    idx += 1
    if length > n:
        break

def solution(left, idx, n):
    if idx < -1:
        return s[n]
    
    if n < dp[idx]:
        return solution(left, idx-1, n)
    elif n >= idx+4 + dp[idx]:
        return solution(left, idx-1, n-(idx+4+dp[idx]))
    else:
        if n - dp[idx] == 0:
            return 'm'
        else:
            return 'o'

print(solution(0, idx-1, n-1))

솔루션1: 최적화

Moo 게임 풀이1

나의 코드를 완전히 최적화시킨 코드가 있어서 가져와보았다. 수열의 길이를 미리 만드는 과정을 생략했다. 나머지는 동일하다.

N = int(input())

def moo(acc, cur, N):
    prev = (acc-cur)//2
    if N <= prev: return moo(prev, cur-1, N)
    elif N > prev+cur: return moo(prev, cur-1, N-prev-cur)
    else: return "o" if N-prev-1 else "m"

acc, n = 3, 0
while N > acc:
    n += 1
    acc = acc*2+n+3

print(moo(acc, n+3, N))

솔루션2: 또 다른 분할정복

Moo 게임 풀이2

아이디어는 유사하면서, 다른 방식으로 재귀를 구현된게 있더라.

import sys

s0 = ['m', 'o', 'o']

def bt(n, depth, b_len):  # depth: 차수, # b_len: 이전 차수의 길이
    # 다음 길이
    new_len = 2 * b_len + depth + 3
    if n <= 3:  # n이 3 이하일 경우 바로 출력
        print(s0[n - 1])
        return

    if new_len < n: # new_len이 n보다 작을 경우
        bt(n, depth + 1, new_len)  # depth(차수)를 하나 늘림. new_len이 n을 담을 수 있을 때까지
    else:
        # n은 b_len(이전 길이)보다 무조건 큼.
        # 가운데
        if b_len < n and n <= b_len + depth + 3:
            if n - b_len != 1:  # n - b_len = 1일때만 'm'이 있고 나머지는 'o'로 채워진다.
                print('o')
            else:
                print('m')
            return
        # 뒤
        else:  # b_len+depth+3 바깥에 있는 경우
            # [n - (b_len + depth + 3)]을 진행해서 다시 첫번째 파트로 돌아온 다음 처음부터 재귀를 돌리기 시작한다.
            bt(n - (b_len + depth + 3), 1, 3)

n = int(sys.stdin.readline().rstrip())
bt(n, 1, 3)