[백준 9095] 1, 2, 3 더하기 / 자바 / dp

#문제         

레벨: S3
알고리즘: dp
풀이시간: 30분 
힌트 참조 유무:

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

---

#문제 풀이        

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

이와 같은 점화식이 세워진 이유는 이러하다. dp[4] = dp[3] +  dp[2] + dp[1] 를 예시로 들어 설명해보겠다. 

        dp[1] = 1;  // 1
        dp[2] = 2;  // 1+1, 2
        dp[3] = 4;  // 1+1+1, 1+2, 2+1, 3

dp[4]는 dp[1] 마지막에 3을 붙이면 되고 dp[2] 마지막에 2를 붙이면 된다. dp[3] 마지막에 1를 붙이면 된다.

1+3

1+1+2, 2+2

1+1+1+1, 1+2+1, 2+1+1, 3+1 

---

#풀이 코드      

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        
        int[] dp = new int[11];
        dp[1] = 1;  // 1
        dp[2] = 2;  // 1+1, 2
        dp[3] = 4;  // 1+1+1, 1+2, 2+1, 3
        
        for (int i = 4; i <= 10; i++) {
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        }
        
        for (int i = 0; i < T; i++) {
            int n = sc.nextInt();
            System.out.println(dp[n]);
        }
        
        sc.close();
    }
}