백준 - 9095(1, 2, 3 더하기) - DP - Java

1. 문제

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

2. 풀이

참고 풀이

점화식을 찾으면 좋겠지만, 단순하게 생각하면 될법한 문제였다. 즉
특정 수를 만들려면

dp[N-1] + 1
dp[N-2] + 2
dp[N-3] + 3

으로 만들어진다는 것이다. 따라서
dp[N] = dp[N-1] + dp[N-2] + dp[N-3]이라는 점화식이 나오는 것이다.

3. 전체 코드

import java.util.*;

public class Main {
    
    public static void main(String args[]) {
        
        Scanner input = new Scanner(System.in);
        
        int T = input.nextInt();
        
        int dp[] = new int[12];
        
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        
        for(int t = 0; t < T; t++) {
            
            int N = input.nextInt();
            
            for(int i = 4; i <= N; i++) {
                dp[i] = dp[i-3] + dp[i-2] + dp[i-1];
            }
            
            System.out.println(dp[N]);
        }
    }
}