5904. Moo 게임

업데이트 시간 : 2023-02-08 11:48:55 +0000

[Gold V] Moo 게임 - 5904

문제 링크

성능 요약

메모리: 31256 KB, 시간: 44 ms

분류

분할 정복(divide_and_conquer), 재귀(recursion)

문제 설명

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 ≤ 10⁹)이 주어진다.

출력

N번째 글자를 출력한다.

💡 Solutions

📄 Moo 게임.py

N = int(input())

def daq(target, length ,cnt):
    if target <= 3:
        return 'm' if target == 1 else 'o'

    count = cnt + 3
    pre = length
    mid = pre + count
    next_length = length*2 + count
    
    pre_length = (length - (count-1))//2
    pre_mid = pre_length + (count-1)
    pre_end = pre_length*2 + (count-1)
    if target > next_length:
        return daq(target, next_length, cnt+1)
    
    elif target <= pre:
        target = target - pre if target - pre > 0 else target 
        return daq(target, pre_length, cnt-1)
    elif target <= mid:
        return 'm' if target == pre + 1 else 'o'
    elif target <= next_length:
        return daq(target-mid, pre_length, cnt-1)
ans = daq(N, 3, 1)
print(ans)