[백준] 9095 1,2,3 더하기 [java]

문제

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

알고리즘 유형 분류

DP

풀이

n을 1,2,3의 합으로 나타낼 수 있는 방법의 수를 구하는 것으로, 전형적인 dp문제이다.
따라서, dp 테이블을 만들고, 초반에 구할 수 있는 수들의 값을 구하고 그 후부터는 문제를 쪼개어 바라봐야 한다.
n == 1 일 때 : 1 (1개)
n == 2 일 때 : 1+1, 2 (2개)
n == 3 일 때 : 1+1+1, 1+2, 2+1, 3 (4개)
여기까지는 직관적으로 쉽게 구할 수 있다.
n == 4 일 때는 4를 쪼개어 생각해야 하는데, 4는 1+3, 2+2, 3+1로 쪼개어 생각할 수 있다.
그러면,
3+1 : n이 3인 경우에 1을 더하는 경우 --> 4개
2+2 : n이 2인 경우에 2를 더하는 경우 --> 2개
1+3 : n이 1인 경우에 3을 더하는 경우 --> 1개
n == 4 일 때 : 7개
n == 5 일 때는 5를 쪼개어 생각해야 하는데, 5는 4+1, 3+2, 2+3으로 쪼개어 생각할 수 있다.
그러면,
4+1 : n이 4인 경우에 1을 더하는 경우 --> 7개
3+2 : n이 3인 경우에 2를 더하는 경우 --> 4개
2+3 : n이 2인 경우에 3을 더하는 경우 --> 2개
n == 5 일 때 : 13개
이렇게 숫자를 쪼개어 1을 더하는 경우, 2를 더하는 경우, 3을 더하는 경우로 볼 수 있다.

코드

import java.util.Scanner;
//
//9095 1, 2, 3 더하기
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int tCase = scanner.nextInt();
        int[] dp = new int[11];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
//
        for(int i = 0; i < tCase; i++){
            int num = scanner.nextInt();
//
            for(int idx = 4; idx <= num; idx++){
                dp[idx] = dp[idx - 1] + dp[idx - 2] + dp[idx - 3];
            }
//
            System.out.println(dp[num]);
        }
    }
}