[Silver Ⅲ] 9461 - 파도반 수열

import java.io.BufferedReader;
import java.io.InputStreamReader;
public class BOJ_9461 { 
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        for(int i = 0; i < N; i++){
            int x = Integer.parseInt(br.readLine());
            long[] dp = new long[Math.max(x+1, 6)];
            dp[1] = dp[2] = dp[3] = 1;
            dp[4] = dp[5] = 2;

            for(int j = 6; j <= x; j++) dp[j] = dp[j-5] + dp[j-1];
            sb.append(dp[x]).append("\n");
        }
        System.out.println(sb);
    }
}

// #2 dp가 int라서 터졌다. long으로 선언해야함.
// public class BOJ_9461 { 
//     public static void main(String[] args) throws Exception{
//         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//         StringBuilder sb = new StringBuilder();
//         int N = Integer.parseInt(br.readLine());
//         for(int i = 0; i < N; i++){
//             int x = Integer.parseInt(br.readLine());
//             if(x == 1){
//                 sb.append(1).append("\n");
//                 continue;
//             }else if(x == 2){
//                 sb.append(1).append("\n");
//                 continue;
//             }else if(x == 3){
//                 sb.append(1).append("\n");
//                 continue;
//             }else if(x == 4){
//                 sb.append(2).append("\n");
//                 continue;
//             }else if(x == 5){
//                 sb.append(2).append("\n");
//                 continue;
//             }

//             int[] dp = new int[x+1];
//             dp[1] = 1;
//             dp[2] = 1;
//             dp[3] = 1;
//             dp[4] = 2;
//             dp[5] = 2;

//             for(int j = 6; j <= x; j++) dp[j] = dp[j-5] + dp[j-1];
//             sb.append(dp[x]).append("\n");
//         }
//         System.out.println(sb);
//     }
// }

// #1 재귀는 시간초과
// public class BOJ_9461 { 
//     public static void main(String[] args) throws Exception{
//         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//         StringBuilder sb = new StringBuilder();
//         int N = Integer.parseInt(br.readLine());
//         for(int i = 0; i < N; i++){
//             int x = Integer.parseInt(br.readLine());
//             sb.append(tri(x)).append("\n");
//         }
//         System.out.println(sb);
//     }

//     public static int tri(int x){
//         if(x == 1) return 1;
//         else if(x == 2) return 1;
//         else if(x == 3) return 1;
//         else if(x == 4) return 2;
//         else if(x == 5) return 2;
//         else return tri(x-1) + tri(x-5);
//     }
// }