백준 9095번: 1, 2, 3 더하기 (Java, 동적 계획법)

☑️ 문제

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

✔️관련 알고리즘 개념

동적 계획법

☑️ 문제 분석

• 여기서 n의 값은 11보다 작은 양수이다.
• n에 대한 경우의 수는 앞의 세 개의 n값들의 합이다.
  • 왜 앞의 3개의 합이냐면 합을 1, 2, 3의 합으로만 나타낼 수 있기 때문이다.
• 아래 그림을 보면
  • 4를 1, 2, 3의 합으로 나타내는 경우의 수는 총 7가지이다.
    • 1을 나타내는 모든 식에 각각 3을 더해주면 4를 나타내는 식이 된다.
    • 2를 나타내는 모든 식에 각각 2를 더해주면 4를 나타내는 식이 된다.
    • 3을 나타내는 모든 식에 각각 1을 더해주면 4를 나타내는 식이 된다.
  • 따라서 여기서 점화식은 p[i] = p[i-1] + p[i-2] + p[i-3] (i > 3) 이 나온다.

☑️ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int[] dp = new int[11]; // n은 11보다 작다고 했으니 0~10까지

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

        // DP 초기화
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        for (int i = 4; i <= 10; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }

        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            int n = Integer.parseInt(br.readLine());
            System.out.println(dp[n]);
        }
    }
}

☑️ 채점 결과 : 맞음

☑️ 어려웠던 점

• 없음