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

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

9095번: 1, 2, 3 더하기

 

정수  n	경우의 수dp	예시
1	dp[1]=1	[1]
2	dp[2]=2	[1+1], [2]
3	dp[3]=4	[1+1+1], [1+2], [2+1], [3]
4	dp[4]=7	[1+1+1+1],[1+1+2],[1+2+1],[1+3] [2+1+1],[2+2] [3+1]
5	dp[5]=13	[1+1+1+1+1],[1+1+1+2],[1+1+2+1],[1+1+3],[1+2+1+1],[1+2+2],[1+3+1]  [2+1+1+1], [2+1+2], [2+2+1], [2+3] [3+1+1], [3+2]

 

정수 n이 4이상일 때

dp[4] = dp[3] + dp[2] + dp[1]

dp[5] = dp[4] + dp[3] + dp[2]

...

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

 

import java.util.*;
import java.io.*;

public class Main {

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer();

        int T = Integer.parseInt(br.readLine());
        int[] dp = new int[11];
        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 num = Integer.parseInt(br.readLine());
            sb.append(dp[num]).append("\n");
        }
        System.out.println(sb);
    }

}