백준 9461번 (점화식)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.*;

import static java.util.Collections.*;

public class Main {
public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    StringBuilder sb = new StringBuilder();


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


    /*
   1 1 1 2 2 3 4 5 7 9 12 16 21


     */

    long[] dp = new long[110];

    dp[0] = 1;
    dp[1] = 1;
    dp[2] = 1;
    dp[3] = 2;
    dp[4] = 2;
    dp[5] = 3;
    dp[6] = 4;




    for (int i = 0 ; i < N; i++)
    {
        int M = Integer.parseInt(br.readLine());


        for (int j = 0 ; j <= M; j ++)
        {
            dp[j+5] = dp[j+4]+dp[j];
        }

        sb.append(dp[M-1]).append("\n");

    }

    System.out.println(sb);














}

}

솔직하게 말하자면 규칙을 찾지 못하여 지피티를 이용하여 문제를 풀었다.
여기선 dp배열을 int로 하면 100을 넣었을 때 값이 int값을 초과하는 런타임오류가 발생한다. 그래서 long으로 변경하면 쉽게 풀린다.