문제

BOJ 5904: Moo 게임 https://www.acmicpc.net/problem/5904

풀이

조건

• N (1 ≤ N ≤ 10^9)이 주어진다.
• Moo 수열은 재귀적으로 만들 수 있다.
• 1보다 크거나 같은 모든 k에 대해서, S(k)는 S(k-1)과 o가 k+2개인 수열 "m o ... o" 와 S(k-1)을 합쳐서 만들 수 있다.
• N이 주어졌을 때, Moo 수열의 N번째 글자를 구한다.

풀이 순서

• N (1 ≤ N ≤ 10^9)이기 때문에 분할 정복을 이용해야한다.
• 크게 앞, 가운데, 뒤 3 파트로 생각할 수 있다.
• 재귀를 돌며 현재 문자열의 길이만 생각하며 입력받은 n이 위의 3 파트 중 어느 파트에 속하는지를 알아낸다.
• 현재의 문자열 길이는 (이전 문자열 길이) X 2 + (현재 차수) + 3 이다.
• 해당하는 파트를 재귀적으로 탐색한다.

코드

Python

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)

정리

• 처음에는 m이 있는 인덱스만을 저장해가며 DP로 해결하려 했지만 메모리 초과가 났다.
• 분할 정복과 재귀를 사용해 해결하는 부분을 더 공부해야겠다.