[python] 백준 5904 :: Moo 게임 (분할정복)

[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번째 글자를 출력한다.

풀이

1. 몇번째 수열에 위치하는지 구하기

• Moo 수열이 최초의 수열인 ["m", "o", "o"]일 경우를 제외하고는
  수열의 총 길이는 이전 수열 길이 * 2와 가운데 추가되는 수열의 길이로 구할 수 있다.
• 가운데 추가되는 수열의 길이는 첫 수열이 0번째라고 했을 때, 수열의 순서 +3으로 구할 수 있다.

total_length = 3  # 처음에는 moo 세글자
n = 0  # 몇번째 수열인지 -> 가운데 길이 구하기 위함
while total_length < N:
    # 기존 수열 * 2 + o 개수 + m 개수
    n += 1
    total_length = 2 * total_length + n + 3

# 가운데 길이 = 수열 순서 + 3
print(recursive(total_length, n+3, N))

 

2. 값을 찾을 수 있는 수열까지 줄여나간다.

• 분할 정복으로, 수열의 길이를 줄여가면서 찾는 순서가
  0번째 수열 혹은 가운데 수열에 위치하는 순간까지 줄이면 결과를 구할 수 있다.

N = int(input())

# 현재 총 길이, 가운데 길이, 구하려는 순서
def recursive(total_length, mid_length, N):

    # 왼쪽 수열 길이 = 가운데를 제외한 반
    left_length = (total_length - mid_length) // 2

    # 찾으려는 순서가 왼쪽 수열에 있으면 -> 그 전 수열로 ㄱ
    if N <= left_length:
        return recursive(left_length, mid_length - 1, N)

    # 찾으려는 순서가 오른쪽 수열에 있으면 -> 왼쪽 수열의 순서로 바꾸고 그 전 수열로 ㄱ
    if N > left_length + mid_length:
        return recursive(left_length, mid_length - 1, N - left_length - mid_length)

 

3. N이 3보다 작아진 경우 결과 리턴

• 0번째 수열에 위치하는 경우에는 ["m", "o", "o"]니까 인덱스로 바로 구하면 된다.

    if N <= 3:
        return "moo"[N-1]

 

4. N이 가운데 수열에 존재하는 경우 결과 리턴

• 가운데 수열에 위치하는 경우에는 첫번째면 m 첫번째가 아니면 o가 된다.

    # 찾으려는 순서가 가운데에 위치할 때
    # 찾으려는 순서가 가운데의 첫번째면 m, 아니면 o
    if N - left_length == 1:
        return "m"
    else:
        return "o"

 

끝!

전체 코드

N = int(input())

# 현재 총 길이, 가운데 길이, 구하려는 순서
def recursive(total_length, mid_length, N):
    if N <= 3:
        return "moo"[N-1]

    # 왼쪽 수열 길이 = 가운데를 제외한 반
    left_length = (total_length - mid_length) // 2

    # 찾으려는 순서가 왼쪽 수열에 있으면 -> 그 전 수열로 ㄱ
    if N <= left_length:
        return recursive(left_length, mid_length - 1, N)

    # 찾으려는 순서가 오른쪽 수열에 있으면 -> 왼쪽 수열의 순서로 바꾸고 그 전 수열로 ㄱ
    if N > left_length + mid_length:
        return recursive(left_length, mid_length - 1, N - left_length - mid_length)

    # 찾으려는 순서가 가운데에 위치할 때
    # 찾으려는 순서가 가운데의 첫번째면 m, 아니면 o
    if N - left_length == 1:
        return "m"
    else:
        return "o"


total_length = 3  # 처음에는 moo 세글자
n = 0  # 몇번째 수열인지 -> 가운데 길이 구하기 위함
while total_length < N:
    # 기존 수열 * 2 + o 개수 + m 개수
    n += 1
    total_length = 2 * total_length + n + 3

# 가운데 길이 = 수열 순서 + 3
print(recursive(total_length, n+3, N))