백준 17297번: Messi Gimossi

문제 설명

• https://www.acmicpc.net/problem/17297
• 주어진 규칙으로 문자열을 만들었을 때 M번째 값이 무엇인지 구하는 문제입니다.

접근법

• 풀이방법을 잘 모르시겠는 분들은 백준 16974번: 레벨 햄버거문제를 먼저 풀어보는걸 추천드립니다.
• 문제의 핵심은 문자열을 직접 구하지 않는 것입니다.
  문자열을 직접 구하지 않고 문제를 풀려면 재귀를 적절히 사용해야 합니다. 재귀가 사용 가능한 이유는 N번째 문자열 = N-1번째 문자열 + 띄어쓰기 + N-2번째 문자열로 구성되기 때문입니다.
  구하는 X값이 N-1번째 문자열의 길이보다 작다면 N-1번째 문자열에서 정답을 구하는 것과 동일합니다.
  구하는 X값이 N-1번째 문자열의 길이 + 1보다 크다면 N-2번째 문자열에서 정답을 구하는 것과 비슷합니다.
  (X - (N-1번째 문자열의 길이 + 1)) 값을 N-2번째에서 찾는 것과 동일합니다.

정답

import java.util.*;
import java.io.*;

public class Main {
	static int N = 42; // 42: 문자열을 만들었을 때 그 길이가 문제에서 주어진 M의 범위((2**30)-1)를 초과하지 않는 가장 큰 수
	static int[] resultLength = new int[N]; 
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int M = Integer.parseInt(br.readLine());
		resultLength[1] = 5;
		resultLength[2] = 13;
		for (int i = 3; i < N; i++) {
			resultLength[i] = resultLength[i-1] + 1 + resultLength[i-2];
		}
		
//		System.out.println(Arrays.toString(resultLength));
		System.out.println(recursion(M,N));
	}
	
	public static String recursion(int X, int depth) {
    	// 기저조건
		if(depth <= 2) {
			return baseCondition(X);
		}
		
        // depth-1번째에서 X를 찾는것과 동일합니다.
		if(X <= resultLength[depth-1]) return recursion(X,depth-1);
        
        // 중간의 띄어쓰기에 딱 걸린 경우입니다. 
		if(X == resultLength[depth-1] +1) return "Messi Messi Gimossi";
        
        // X가 depth-2번째 문자열에 포함되는 경우입니다.
		if(resultLength[depth-1]+1 < X && X < resultLength[depth]) return recursion(X-(resultLength[depth-1]+1),depth-2);
        
        // X가 depth번째 문자열의 길이와 동일한 경우입니다.
		if(X == resultLength[depth]) return "i";
		
		return "";
	}
	
	public static String baseCondition(int X) {
		if(X == 1) return "M";
		if(X == 2) return "e";
		if(X == 3 || X == 4 || X == 11 || X == 12) return "s";
		if(X == 5 || X == 8 || X == 13) return "i";
		if(X == 6) return "Messi Messi Gimossi";
		if(X == 7) return "G";
		if(X == 9) return "m";
		if(X == 10) return "o";
		return "";
	}
	
}