백준 9461번 파도반 수열(Java)

1.문제

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

2.풀이

삼각형이 6번째 일 경우 첫번째와 다섯번째를 더했을 경우에 값이 나오는데 확인차 7번째와 8번쨰도 확인해보면 2 + 6 과 3 + 7일때 같은 값이 나오는 걸 알 수 있다.
따라서 규칙 dp[n] = dp[n - 1] + dp[n - 5] 를 이용하면 된다.

3.코드

package com.example.baekjoon;

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

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

        long dp[];

        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            dp = new long[101];

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

            for (int j = 6; j <= n; j++) {
                dp[j] = dp[j - 5] + dp[j - 1];
            }
            System.out.println(dp[n]);
        }
    }
}