[Messi Gimossi/G4/Python3, C++]

 

17297번 Messi Gimossi G4

 

문제
메시는 축구 선수이다. 메시는 기분이 좋다.
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 ≤ 2^30-1)

출력
N이 충분히 클 때, messi(N)의 M번째 글자가 공백(' ')이 아닐 경우에는 그 글자를 출력한다. M번째 글자가 공백(' ') 일 경우에는 Messi Messi Gimossi를 출력한다.정답은 대소문자를 구분하므로 출력에 주의한다.

 

 

다이나믹 프로그래밍, 재귀

 

문자열을 직접 대입해서 풀이하는 방식으로는 메모리 제한에 걸리게 된다.

M의 최대 입력 값인 2^30-1은 1,073,741,823이고, 해당 값을 가질 수 있는 최소의 N은 40이다.  1,119,972,817개

문자 1개 당 1바이트이므로 1.1GB 이상의 값을 요구한다. 512MB라는 제한에 2배가 넘어가는 것이다.

 

 

위 문제를 풀기 위해서는 문자열의 길이를 이용해야 한다.

messi(i) = messi(i-1) + messi(i-2) + 1 이므로, i-1과 i-2의 길이를 알고 있다면 구할 수 있다.

가독성을 위해 m번째 문자열을 m-1번째 인덱스로 바꾸어 구현하였다.

 

모든 messi는 messi(1)과 messi(2)로 이루어져 있으므로 재귀적인 방식으로 원하는 문자열이 속한 messi를 구하게 된다.

구하는 로직은 다음과 같다.

 

1. 현재는 messi(v)이다.

2. m이 messi(v-1)에 속하면 해당 messi(v-1)로 다시 탐색한다.

3. m이 messi(v-1) + 1칸이라면, 공백이므로 "Messi Messi Gimossi"를 출력한다.

4. 2,3이 아니라면 m은 messi(v-2)에 속하기 때문에, 필요 없는 칸(messi(v-1) + 1) 만큼 m에서 빼고 다시 탐색을 진행한다.

 

기저 조건의 경우는 다음과 같다.

1. v가 0 혹은 1이라면 직접 문자열에 접근한다.

2. 공백일 시 "Messi Messi Gimossi"를 출력하고 아니라면 해당 문자를 출력한다.

 

해당 로직을 기반으로 구현한 Python3과 C++의 코드이다.

 

import sys

dp = [0] * 40
res = ["Messi","Messi Gimossi"]

dp[0] = 5
dp[1] = 13
for i in range(2, 40):
    dp[i] = dp[i-1] + 1 + dp[i-2]

m = int(sys.stdin.readline())
m -= 1

def find(v):
    global m
    if v == 0:
        print(res[0][m] if res[0][m] != " " else "Messi Messi Gimossi")
        return
    if v == 1:
        print(res[1][m] if res[1][m] != " " else "Messi Messi Gimossi")
        return
    
    if m < dp[v-1]:
        find(v-1)
    elif dp[v-1] == m:
        print("Messi Messi Gimossi")
        return
    else:
        m -= (dp[v-1]+1)
        find(v-2)
        
find(39)

 

 

#include <iostream>
#include <cctype>

using namespace std;


int dp[40];
string res[2];
int m;

void find(int v)
{
    if (v == 0 || v == 1)
    {
        if (isspace(int(res[v][m])))
            cout<<"Messi Messi Gimossi";
        else
            cout<<res[v][m];
        return;
    }

    if (m < dp[v-1])
    {
        find(v-1);
    }
    else if (m == dp[v-1])
    {
        cout<<"Messi Messi Gimossi";
        return;
    }
    else
    {
        m -= dp[v-1]+1;
        find(v-2);
    }
}

int main()
{
    dp[0] = 5;
    dp[1] = 13;

    
    res[0] = "Messi"; //길이 5
    res[1] = "Messi Gimossi"; //길이 13

    for (int i = 2; i < 40; ++i)
        dp[i] = dp[i-1] + dp[i-2] + 1;

    cin>>m;
    --m;

    find(39);
}