[백준]9461 파도반 수열

비교적 쉽게 풀 수 있었던 dp 문제!

package baekjoon;

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

public class Main_9461 {
    static long[] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        /*

        역삼각형을 만들땐 전 정삼각형의 변 두개의 합
        정삼각형을 만들땐 전 역삼각형의 변 두개의 합

        점화식 도출하면?
        dp[i] = dp[i-1]+dp[i-5]
        */
        dp = new long[101];
        for (int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());
            // 초기값 세팅
            dp[1] = 1;
            dp[2] = 1;
            dp[3] = 1;
            dp[4] = 2;
            dp[5] = 2;
            for (int j = 1; j <= N; j++) {
                dp(j);
            }
            System.out.println(dp[N]);
        }
    }
    static long dp(int N) {
        if(N<=5) return dp[N];
        dp[N] = dp[N-1] + dp[N-5];
        return dp[N];
    }
}

규칙을 찾았더니 정삼각형은 역삼각형 두개의 변으로 만들어지고 역삼각형은 정삼각형 두개의 변으로 만들어졌다. 만들어지는 변의 인덱스를 찾아보니 i-1과 i-5번째임을 알 수 있었고 점화식을 도출하면?
dp[i] = dp[i-1] + dp[i-5]

처음에 틀렸던 이유는 배열을 int[] 로 선언해줘서 특정 N값 이상부턴 값이 커져서 담을 수 없었다.
long[]으로 고쳐주니 성공 !!! 오랜만에 자괴감 안느낀 dp 문제 ㅎㅎ (실버3이긴 하지만..)