9095_1, 2, 3 더하기

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

다이나믹 프로그래밍 강의 들으면서 풀어보는중..

O(TN)

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));
        
        int cnt = Integer.parseInt(br.readLine());
         
        int[] array = new int[10];
        array[0] = 1;
        array[1] = 2;
        array[2] = 4;
            
        for(int i =3; i < 10; ++i)
        {
            for(int j = 1; j < 4; ++j)
            {
                array[i] += array[i-j];
            }            
        }
        
        int num = 0;
        for(int i = 0; i < cnt; ++i)
        {
             num = Integer.parseInt(br.readLine());
             System.out.println(array[num-1]);
        }
        
    }

}

import java.io.*;
public class Main
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());

        int[] arr = new int[T];
        for (int i = 0; i < T; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        for (int i = 0; i < arr.length; i++) {

            int N = arr[i];
            int[] dp = new int[Math.max(4, N+1)];
            dp[1] = 1;
            dp[2] = 2;
            dp[3] = 4;

            for (int j = 4; j <= N; j++)
            {
                for (int k = j-3; k < j; k++)
                {
                    dp[j] += dp[k];
                }
            }

            System.out.println(dp[N]);
        }

    }
}