[분할정복] MOO게임

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

5904번: Moo 게임

 

이 문제는 분할 정복으로 풀어야 하는 문제 중 하나이다.

 

처음 접근을 할때 10**9의 문자열 길이까지 가능하기 때문에 문자열을 직접 만들면서 실행하면 시간초과나 메모리 초과가 날 것을 알았지만 그래도 한번 해봤었고 역시나 메모리 초과가 나왔다.

 

메모리 초과를 해결하기 위해서는 각각 단계를 분할해서 문제를 해결해야 한다.

 

moo는 기본적으로 

 

- S(n-1) + m + (n+2) + S(n-1) 의 값을 가지는데

 

처음에 N을 구할수 있는 최소 값인 acc를 먼저 구하고 구한 acc값을 바탕으로

 

acc값 중에서 N이 왼쪽 S(n-1)에 있는지 중간에 있는지 오른쪽에 있는지 찾아서 

 

중간에 왔을 때 0의 값을 가지면 m이고 다른 값을 가졌을 때 o를 반환하도록 만들면 된다.

 

코드를 보면 더 이해하기 편할 것이다.

 

from sys import stdin as s
import sys
sys.setrecursionlimit(10**6)
s = open('input.txt','rt')

N = int(s.readline())

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))