[JAVA / 자바] 백준 9095번_1, 2, 3 더하기

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

9095번: 1, 2, 3 더하기

---

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

public class Main {
    static int[] dp = new int[11];
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        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];
        }
        while (T-- > 0) {
            int n = Integer.parseInt(br.readLine());
            sb.append(dp[n]).append("\n");
        }
        System.out.print(sb);
    }
}

💡 동적 계획법 (DP)

풀이

- 더할 수 있는 숫자는 1, 2, 3이므로 dp[k-1]까지 모든 값을 안다고 가정했을 때

  → dp[k] = dp[k-1] (+1 하는 경우) + dp[k-2] (+2 하는 경우) + dp[k-3] (+3 하는 경우)

- dp[1] = 1, dp[2] = 2, dp[3] = 4 (3, 2/1, 1/2, 1/1/1)

  → dp[4] = 7, dp[5] = 13, dp[6] = 24, dp[7] = 44 ...