[BOJ] 17297 : Messi Gimossi(Java)

문제

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

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를 출력한다.

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

---

💡 풀이

위의 예시에서 보이는 것과 같이 messi(N)의 길이는 다음과 같이 정의될 수 있다.

$$messi(N) = messi(N-1) + 1 + messi(N-2)$$

그럼 주어진 M에 대해 다음과 같은 3가지의 경우로 나눌 수 있다.

1. M이 messi(N-1)보다 같거나 작은 경우. 즉, messi(N-1) 안에 있는 경우
2. M이 messi(N-1)+1인 경우. 이 경우에는 공백에 해당된다. 
3. M이 messi(N-1)+1보다 큰 경우. 이 경우는 messi(N-2) 안에 있는 경우이다.

처음에 M의 크기를 보고 몇 번째의 messi에 해당하는지 확인한 뒤, 위의 3가지 경우를 확인해가며 N을 줄여나가 N이 1 혹은 2가 되는 경우까지 재귀를 통해 진행시킨다. N이 1 혹은 2에 도달하면 줄여왔던 길이 M을 통해 해당하는 문자를 구할 수 있다. 

즉, 여기서 base case가 N=1 혹은 N=2가 되는 경우 또는 공백을 만난 경우이다. 

 

전체적인 코드는 다음과 같다.

import java.util.Scanner;

public class Q17297 {
    public static long[] messi = new long[1000];
    public static int flag = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long M = sc.nextLong();

        messi[1] = 5;
        messi[2] = 13;

        int index = 3;
        // 현재 주어진 M이 해당하는 messi의 index값(N값) 찾기
        while(true){
            messi[index] = messi[index-1]+1+messi[index-2];
            if(messi[index]>M){
                break;
            }
            index++;
        }

        find(index, M);

    }

    public static void find(int index, long n){
        if(flag==1){
            System.out.println("Messi Messi Gimossi");
            return;
        }
        if(index==1){
            System.out.println("Messi".charAt((int)n-1));
            return;
        }
        else if(index==2){
        	// Messi Gimossi에서 공백을 만났을 경우
            if(n==6){
                System.out.println("Messi Messi Gimossi");
            }
            else
                System.out.println("Messi Gimossi".charAt((int)n-1));
            return;
        }

        // 앞 쪽에 해당하는 경우
        if(messi[index-1]>=n){
            find(index-1, n);
        }
        // 중간의 공백에 해당하는 경우
        else if(messi[index-1]+1==n){
            flag=1;
            find(index-1, n);
        }
        // 뒤 쪽에 해당하는 경우
        else{
            // 앞의 messi(n-1)과 공백의 크기를 전체 길이에서 빼주어야 한다.
            find(index-2, n-messi[index-1]-1);
        }

    }


}