백준 5904 파이썬(Python) 문제풀이 Moo

문제풀이: https://www.acmicpc.net/problem/5904

5904번: Moo 게임

다루는 주제: 분할정복

# n 에서 전차수를 뺄때 1이면 n return은 m이다 나머진 전부 o
# 새로운 차수 = S(k-1) + oxk+m + S(k-1)  새로운차수 길이 = 전차수 + 3 + 전차수
# n이 l보다 크고 다음 차수로 가는 필요길이보다 작을때만
#  +++ l다음 글자는 무조건 m이다
import sys


def moo(n, k, l):  # n번째 글자,k는 차수, #l은 전 차수의 길이
    S0 = ['m', 'o', 'o']
    lk = l + k + 3 + l  # 새로운 차수의 길이
    if n <= 3:  # 3보다 작을때
        print(S0[n - 1])
        return
    if lk < n:  # lk가 n보다 작을 경우 차수 올리기
        moo(n, k + 1, lk)
    else:
        if l < n <= l + k + 3:  # n이 전차수길이 보다 크고 다음 차수로 가는 필요길이보다 작을떄
            if n - l == 1:  # n-l = 1일때만 m 아니면 o
                print('m')
            else:
                print('o')
            return
        else:  # 범위안에 없을떄 재귀
            moo(n - (l + k + 3), 1, 3)


N = int(sys.stdin.readline())
moo(N, 1, 3)