백준 9095번: 1, 2, 3 더하기의 점화식

순서가 다르면 다른 경우입니다

백준 9095번은 정수 N을 1, 2, 3의 합으로 나타내는 경우의 수를 구하는 문제입니다. 하나 이상의 수를 사용해야 합니다. 그리고 1 + 1 + 2와 2 + 1 + 1은 서로 다른 경우로 셉니다.

직접 세어 본 값에서 점화식으로

처음에는 작은 수의 경우를 세었습니다. dp[1] = 1, dp[2] = 2, dp[3] = 4, dp[4] = 7입니다. 5까지 세면 13이 되는데 수가 커질수록 하나씩 나열하기는 번거로워집니다.

이 값들에서 앞의 세 값을 더하는 규칙을 찾았습니다.

dp[n] = dp[n - 1] + dp[n - 2] + dp[n - 3]

마지막에 더하는 수를 기준으로 나눠 보면 이유가 보입니다. 마지막 수가 1인 경우는 n-1을 만드는 경우, 2인 경우는 n-2를 만드는 경우, 3인 경우는 n-3을 만드는 경우와 각각 대응합니다.

당시에는 7까지 세어 보고 점화식으로 구한 값 44와 맞는지 확인했습니다. 코드에서는 처음 세 값을 넣고 4부터 필요한 값을 미리 계산해 저장한 뒤 각 입력에 해당하는 값을 출력합니다.

제출 코드

Java

import java.io.*;

class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());

        // 1~11
        int[] dp = new int[12];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        for (int i = 4; i <= 11; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }
        for (int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());
            bw.write(String.valueOf(dp[N]));
            bw.write("\n");
        }
        bw.flush();
    }
}