DP - 백준9590 1, 2, 3 더하기

처음 보고 고민해 본 결과 아무리 봐도 백트래킹 문제와 유사해 보였고, 이걸 어떻게 DP로 푸나 도저히 감이 안 왔다.
그래서 바킹독 선생님의 힌트를 조금 얻어 풀게 되었다.

힌트 :
N = 4일 때,
1(+3)
1+1(+2), 2(+2)
1+1+1(+1), 3(+1), 2+1(+1), 1+2(+1)

이 힌트의 내용은 즉, N은
N-3인 경우의 수들에 모두 +3을 하는 경우
N-2인 경우의 수들에 모두 +2를 하는 경우
N-1인 경우의 수들에 모두 +1을 하는 경우
를 모두 더한 것이다.

N-1인 경우의 수들에 모두 +1을 하는 경우는, 총 N-1의 경우의 수와 같다.
(힌트를 참고하면 N-1인 경우의 수는 1+1+1, 3, 2+1, 1+2 총 4개이므로, 여기서 각각 +1을 하는 경우의 수는 마찬가지로 4이다)
N-2와 N-3도 마찬가지다.

따라서 점화식은 dp[n] = dp[n-3] + dp[n-2] + dp[n-1] 로 도출된다.

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //점화식
        // 1 : 1
        // 2 : 11, 2
        // 3 : 111, 12, 21, 3
        // 4 : 1(+3) / 11(+2), 2(+2) / 111(+1), 12(+1), 21(+1), 3(+1)
        // dp[n] = dp[n-3] + dp[n-2] + dp[n-1]
        int[] table = new int[11];
        table[1] = 1;
        table[2] = 2;
        table[3] = 4;
        for(int i = 4; i < 11; i++){
            table[i] = table[i-1]+ table[i-2] + table[i-3];
        }
        int t = Integer.parseInt(br.readLine());
        for(int i = 0; i < t; i++){
            int n = Integer.parseInt(br.readLine());
            System.out.println(table[n]);
        }
    }
}

* 문제의 범위가 1 ~ 10이므로 table[1] ~ table[10]까지 저장해놓고, 주어진 테스트케이스의 수 만큼 반복해서 꺼내 출력