[백준/Java] 2502번 떡 먹는 호랑이

-Code

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

public class BOJ2502 {
    static int[] dp;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int day = Integer.parseInt(st.nextToken());
        int cnt = Integer.parseInt(st.nextToken());

        solve(cnt, day);

        System.out.println(dp[1]);
        System.out.println(dp[2]);
    }

    private static void solve(int cnt, int day) {
        for (int i = 0; i < cnt; i++) {
            dp = new int[day + 1];
            for (int first = 1; first < cnt; first++) {
                for (int second = 1; second < cnt; second++) {
                    dp[1] = first;
                    dp[2] = second;
                    for (int j = 3; j <= day; j++) {
                        dp[j] = dp[j - 1] + dp[j - 2];
                    }

                    if (dp[day] == cnt) {
                        return;
                    }
                }
            }
        }
    }
}

범위가 작아서 모든 경우의 수를 대입해도 풀리긴 했습니다. 그러나 다음과 같이하면 더 빠르게 풀 수 있음도 찾아서 알게 되었습니다.

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

public class BOJ2502 {
    public static void main(String[] args) throws IOException {
        BufferedReader br =
                new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int days = Integer.parseInt(st.nextToken());
        int cnt = Integer.parseInt(st.nextToken());

        int[] firstDp = new int[days + 1];
        firstDp[1] = 1;
        firstDp[2] = 0;
        int[] secondDp = new int[days + 1];
        secondDp[2] = 1;
        // 마지막 x, y의 곱을 구하기
        for (int i = 3; i <= days; i++) {
            firstDp[i] = firstDp[i - 2] + firstDp[i - 1];
            secondDp[i] = secondDp[i - 2] + secondDp[i - 1];
        }
        // 계산
        for (int a = 1; a <= cnt; a++) {
            // 해당 일의 값에서 x를 계산한 값을 빼서 남은 값으로 
            // 두번째 수 계산
            int now = cnt - (firstDp[days] * a);
            if (now % secondDp[days] == 0) {
                System.out.println(a);
                System.out.println(now / secondDp[days]);
                break;
            }
        }
    }
}

위와 같이 어차피 두 수가 (i - 2) + (i - 1) 인덱스의 합을 각각 구해서 더한 값이 해당 일의 값이므로 미리 days의 계산 식을 dp로 구하고 cnt까지 반복하면서 "cnt - (첫 번째 값 * day에 맞는 곱)"에서 "두 번째 값에 곱해야 할 수"로 나누었을 때 0이 나오면 값이 존재하므로 그때 첫 번째 값과 두 번째 값은 "cnt - (첫 번째 값 * day에 맞는 곱) / 두 번째값"을 해주게 되면 값이 나오게 되어 출력하면 됩니다.