[WEEK01/DAY06] 백준 문제 : Moo 게임

https://www.acmicpc.net/problem/5904

5904번: Moo 게임

 

즐겁게 할 수 있는 술게임이라는 말에 혹해서 골랐다가, 생각보다 어려워서 애를 먹었다.

 

문제 설명 :

m o o가 특정 규칙에 따라 나열된다.

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"

위와 같이 S(0)은 길이가 3인 수열 "m o o"이고,

S(k)는

 

S(k-1) +

o가 k+2개인 "m o ... o" +

S(k-1)

 

과 같이 구성된다. (k는 1보다 크거나 같은 모든 정수)

이런 식으로 만들면 길이가 무한대인 문자열을 만들 수 있고, 그 수열을 Moo 수열이라고 한다.

N이 주어졌을 때, Moo 수열의 N번째 글자를 구하는 프로그램을 작성해야 한다.

 

문제 풀이 :

나는 m이 나오는 위치를 계산하기로 했다.

m이 나오는 위치가 아니면 모두 o를 출력하면 되기 때문이다.

 

m은 1, 4, 8, 11, 16, 19, 23, 26, ... 의 위치에 있다.

 

이들 숫자 사이의 규칙은, 마치 이진 트리와 같은 형식의 공차를 가지고 있다는 것이다.

 

예를 들면 S(2)인 Moo 수열에서:

이렇게 양 끝의 값이 정해져 있다고 할 때, m값 사이의 공차는 3, 4, 3, 5, 3, 4, 3인데

이는 중앙값을 기준으로 양쪽이 대칭인 트리처럼 내려가는 형태이다.

 

단, 이 방법은 문제에서 주어진 것처럼 수열이 무한히 확장되는 경우에는 부적합하다.

수열에 끝이 없기 때문에 양 끝의 기준점을 잡기가 불가능하기 때문이다.

 

다행히 입력 제한사항에 N이 1 ≤ N ≤ 1,000,000,000(십억) 이라고 나와 있었기에, 나는 S(27)의 값인 1,073,741,792를 기준으로 잡고 공차를 계산하였다.

 

 

 

다른 사람의 문제 풀이를 보니 N값을 줄여 나가면서 푸는 방법도 있었는데, 그 방법이 무한한 수를 계산할 수 있는 알고리즘이기 때문에 더 적합하다고 생각한다.

 

 

아래는 내가 제출한 정답 코드이다.

 

def moo(left, right, gap):
    if gap == 3:
        if n == left or n == right: print('m')
        else: print('o')
    else:
        if n < (right-left)/2 + left + gap/2 and n >= (right-left)/2 + left - gap/2 :
            if n == (right-left)/2 + left - gap/2: print('m')
            else: print('o')

        elif n < (right-left)/2 + left - gap/2:
            moo(left, (right-left)/2 + left - gap/2, gap-1)

        else:
            moo((right-left)/2 + left + gap/2, right, gap-1)


n = int(input())
n = n-1

left = 0
right = 1073741792  # full range of n
gap = 30

moo(left, right, gap)