백준 - 파도반 수열

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        long[] arr = new long[101];
        arr[1] = 1;
        arr[2] = 1;
        arr[3] = 1;
        arr[4] = 2;
        for (int i = 5; i < arr.length; i++) {
            arr[i] = arr[i-1] + arr[i-5];
        }
        for (int i = 0; i < T; i++) {
            int v = sc.nextInt();
            System.out.println(arr[v]);
        }
    }
}

🫡패턴을 파악했다면 풀 수 있는 문제입니다.
dp[i] = dp[i-1] + dp[i-5]식에 대입해보면 해당 결과 값이 P(N)을 가리키고 있다는 것을 알 수 있습니다.

위 문제에서 조심할 점은 int값을 결과 값으로 할 경우 값이 초과되어 마이너스가 나오게 되므로 long형태로 반환해주면 됩니다.

출처 : 백준 - 파도반 수열