[Silver Ⅲ] 9095 - 1, 2, 3 더하기

import java.io.BufferedReader;
import java.io.InputStreamReader;
public class BOJ_9095 {  // 무한배낭이지만 순서 있는 경우
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        int[] testCase = new int[3];
        for(int i = 0; i < testCase.length; i++) testCase[i] = i+1;   
        for(int i = 0; i < N; i++){
            int target = Integer.parseInt(br.readLine());
            int[] dp = new int[target + 1];
            dp[0] = 1;
            for(int j = 1; j <= target; j++){
                for(int k = 0; k < testCase.length; k++){
                    if(j - testCase[k] >= 0) dp[j] += dp[j - testCase[k]]; 
                } 
            } 
            sb.append(dp[target]).append("\n");
        }    
        System.out.println(sb);
    }
}

// 무한배낭식 -> 순서고려 되지 않음. 4 8 14 나옴
// public class BOJ_9095 {  
//     public static void main(String[] args) throws Exception{
//         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//         int N = Integer.parseInt(br.readLine());
//         StringBuilder sb = new StringBuilder();

//         for(int i = 0; i < N; i++){
//             int target = Integer.parseInt(br.readLine());
//             int[] dp = new int[target + 1];
//             dp[0] = 1;
//             for(int j = 1; j <= 3; j++){
//                 for(int k = j; k <= target ; k++){
//                     dp[k] += dp[k - j]; 
//                 } 
//             } 
//             sb.append(dp[target]).append("\n");
//         }    
//         System.out.println(sb);
//     }
// }