[BOJ - JAVA] 2502 - 떡 먹는 호랑이(DP)

# 주소

https://www.acmicpc.net/problem/2502

2502번: 떡 먹는 호랑이

# 문제

# 문제 해설 및 코드 리뷰

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main{
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
    	int[] dp = new int[n];
    	
    	for(int i = 1; i <= m/2; i++) {
    		for(int j = i+1; j < m; j++) {
    			dp[0] = i;
    			dp[1] = j;
    			for(int k = 2; k < n; k++) {
    				dp[k] = dp[k-1] + dp[k-2];
    			}
    			if(dp[n-1] == m) {
    				System.out.println(dp[0]);
    				System.out.println(dp[1]);
    				System.exit(0);
    			}
    		}
    	}
    }
}

문제에서 알 수 있듯이 일단 dp의 첫 번째 인덱스와 두 번째 인덱스의 값을 알아내야 합니다.

Scanner로 입력 받으면 시간 초과가 나기 때문에 성능이 가장 좋은 Buffered를 이용해줍니다.

기본적으로 i보다 j가 더 커야하기 때문에 모든 경우의 수에 대비해 i = 1부터, 그리고 j는 i+1부터 dp[n]의 값을 유추해야합니다. 그리고 이 dp의 수열은 피보나치수열이기 때문에 정해지는 dp[0]과 dp[1]의 값에 따라 dp[n]의 값은 상이할 수 있습니다. 그렇게 계속해서 dp[0]과 dp[1]을 변경해주다, dp[n]의 값이 m과 일치하면 dp[0]과 dp[1]을 출력하는 방식입니다.

원래는 수학을 이용하여 dp[n]에 dp[1]과 dp[n]이 몇 개 들어있는지 규칙을 찾으려 했으나, 규칙이 없어서 그냥 코딩으로 푸는게 낫다고 판단했습니다.

꼭 출력하고 System.exit(0)을 하여 그 이상의 for문을 가동하는 일이 없어야 정답이 출력됩니다. 유념해주시기 바랍니다.

 

감사합니다.