[SW사관학교 정글] Week01 알고리즘 시험 - BOJ 5904번 moo 게임

 

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

시행착오: 단순 재귀함수로 생각하고 접근했었음

def moo(k):
    if k==0:
        return "moo"
    return moo(k-1) + "m" + "o"*(k+2) + moo(k-1)
for i in range(int(N ** (1/2))):
    if len(moo(i)) > N:
        K = i
        break
# print(len(moo(N)))
# print(K)
# print(moo(K))
print(moo(K)[N-1])

 

문제 핵심:

S(k) = S(k-1) + "m" + "o" * (k+2) + S(k-1)

얼핏보면 재귀함수로 문자열을 저장하면될것처럼 보이는 단순한 문제이지만 입력값 N의 범위가 10^9 이기때문에 문자열을 저장해서 인덱스를 찾으려고하면 메모리 초과가 날수밖에없다.

핵심은 문자열의 길이는 규칙적으로 증가하므로 (현재길이) = (이전길이) *2 + K+3

앞부분 S(k-1) 인지  moo... 부분인지 뒷부분 S(k-1) 부분인지 구별하고 moo... 부분에 있는것으로 판단되면 첫번째 인덱스면 m 나머지 부분이면 o를 리턴하면 된다.

 

풀이 코드

import sys
sys.setrecursionlimit(1000000)		# 파이썬 재귀 제한 해제		
N = int(sys.stdin.readline().strip())
K = 0
Length = 3				# 기본 moo 길이
while Length < N:			# 주어진 N을 만족하는 k값찾기
    K += 1
    Length = 2 * Length + (K + 3)	# 현재길이 = 이전길이*2 + k + 3
# print(K)
def find_n(k,n,length):
    global prev_len
    if k == 0:				# 종료조건
        return "moo"[n-1]   
    prev_len = (length-(k+3)) // 2
    mid_len = k + 3						
    if n < prev_len:			# 앞부분
        return find_n(k - 1, n,prev_len)
    elif n < prev_len + mid_len:	# moo... 부분
        if n == prev_len+1:
            return "m"
        else:
            return "o"
    else:				# 뒷부분
        return find_n(k - 1, n - prev_len - mid_len,prev_len)

print(find_n(K,N,Length))