5904번: Moo 게임

풀이

만약 이 문제를 전체 moo 수열을 직접 만들어서 풀려 하면 시간 초과 및 메모리 초과가 뜰 것이다. 재귀 함수를 사용하되, 최대한 light하게 만들어 진행하는 것이 최우선이다.

따라서 직접 수열을 만들지 않더라도 주어진 n의 글자를 알아야 한다.

• n번째 글자가 몇 S(k)에 속해 있는가?
  • 글자 수에 대한 점화식(?)이 필요하다. 간단하므로 그냥 while문을 사용하는 것도 좋다.
• S(k)의 ①S(k-1) + ②'moo'*k + ③S(k-1) 이렇게 3개의 부분 중 어느 부분에 n번째 글자가 속해 있는가?
  • 만약 ①에 속해 있다면 재귀를 타고 S(k-1)에 대해 찾아보면 된다.
  • ②에 속해 있다면 맨 처음 글자는 m, 나머지는 o일 것이다.
  • ③에 속해 있다면 n의 수만 조정하여 ①과 같이 수행한다.
  • 이를 위해 재귀함수에는 k(함수의 차수), n(찾고자 하는 숫자의 순서)가 들어가야 한다.

맞은 풀이

import sys
input = sys.stdin.readline

def find_m(k, leng, n):
    if k == 0:  # 초기값
        if n == 0:
            return 'm'
        else:
            return 'o'

    len_before = (leng-k-3)//2

    if 0 <= n < len_before:
        return find_m(k-1, len_before, n)
    elif n == len_before:
        return 'm'
    elif len_before < n < len_before + (3+k):
        return 'o'
    elif n >= len_before + (3+k):
        return find_m(k-1, len_before, n-(3+k)-len_before) 

if __name__ == '__main__':
    n = int(input())

    # n이 속해 있는 S(k)의 k값을 구하라.
    k = 0
    leng = 3
    while leng < n:
        k += 1
        leng = leng*2 + 3 + k

    print(find_m(k, leng, n-1))

틀린 풀이. 모든 문자열을 재귀함수로 구현하려 했었음

import sys
input = sys.stdin.readline

n = int(input())

def moo(n):
    if n == 0:
        return 'moo'

    return moo(n-1)+ 'moo' + 'o'*n + moo(n-1)

def len_of_moo(n):
    if n == 0:
        return 3
    
    return len_of_moo(n-1) * 2 + n + 3

k = 0

for i in range(1, n):
    if n < len_of_moo(i):
        k = i
        break

print(moo(k)[n-1])