[Java] 백준 9095번 - Dynamic Programming

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

public class s3_9095{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++){
            bw.write(String.valueOf(count(Integer.parseInt(br.readLine()))));
            bw.newLine();
        }
        bw.flush();
        bw.close();
    }

    public static int count(int n){
        int[] ary = new int[3];
        // ary[0] : 3의 개수, ary[1] : 2의 개수, ary[2] : 1의 개수
        ary[0] = n / 3;
        ary[1] = (n % 3) / 2;
        ary[2] = n - ary[0] * 3 - ary[1] * 2;

        int cnt = 0;

        while (ary[0] != -1){
            while (ary[1] != -1){
                cnt += factorial(ary[0] + ary[1] + ary[2]) / (factorial(ary[0]) * factorial(ary[1]) * factorial(ary[2]));
                ary[1]--;
                ary[2] += 2;
            }
            ary[0]--;
            ary[1] = (n - ary[0] * 3) / 2;
            ary[2] = n - ary[0] * 3 - ary[1] * 2;
        }

        return cnt;
    }

    public static int factorial(int k){
        int cnt = 1;
        for (int i = 2; i <= k; i++){
            cnt *= i;
        }
        return cnt;
    }
}