문제

메시는 축구 선수이다. 메시는 기분이 좋다.

messi(1): Messi

messi(2): Messi Gimossi

messi(3): Messi Gimossi Messi

messi(4): Messi Gimossi Messi Messi Gimossi

messi(5): Messi Gimossi Messi Messi Gimossi Messi Gimossi Messi

메시의 외침은 피보나치 수열과 유사하게 정의된다. messi(N)은 messi(N-1), 공백, messi(N-2)을 차례로 이어붙여서 만든 문자열이다.

욱제는 N이 충분히 클 때, messi(N)의 M번째 글자가 뭔지 궁금해졌다.

입력

정수 M이 주어진다. (1 ≤ M ≤ 230-1)

출력

N이 충분히 클 때, messi(N)의 M번째 글자가 공백(‘ ‘)이 아닐 경우에는 그 글자를 출력한다.

M번째 글자가 공백(‘ ‘)일 경우에는 Messi Messi Gimossi를 출력한다.

정답은 대소문자를 구분하므로 출력에 주의한다.

문제 링크

My solution (Python)

import sys


def find(idx, M, dp):
    if idx <= 1:
        return "Messi Gimossi"[M - 1]
    if M > dp[idx - 1] + 1:
        res = find(idx - 2, M - dp[idx - 1] - 1, dp)
    elif M < dp[idx - 1]:
        res = find(idx - 1, M, dp)
    else:
        return " "
    return res


M = int(sys.stdin.readline())
dp = [5, 13]
while dp[-1] < M:
    dp.append(dp[-2] + 1 + dp[-1])
res = find(len(dp) - 1, M, dp)
print("Messi Messi Gimossi" if res == " " else res)

My logic & Feedback

문제 유형은 DP / 분할정복이다.

피보나치이기 때문에 두 가지 유형 전부 적용될 것 같다.

풀이는, 우선 문자 ‘길이’를 input M만큼 길어질 때 까지 dp배열에 bottom-up으로 전부 저장한다.

그다음 find함수로 재귀를 타면서 분할정복을 하는데,

해당 문자가 피보나치이므로 분할할 조각 또한 피보나치 조각으로 나눈다.

M이 현재 dp배열 index - 1 의 수보다 크면 현재 문자를 2조각으로 잘랐을 때 뒤의 조각으로 재귀를 타고(공백이 붙으므로 -1을 해준다),

작으면 현재 dp배열 index - 1 의 조각으로 재귀를 탄다.

M이 공백 위치에 닿거나, dp배열의 1 이하 조각에 닿으면,

그에 맞는 값을 리턴하면 된다.