[백준] 9461: 파도반 수열

문제

문제풀이

6번째 삼각형부터 i-1번째 삼각형의 변과 i-5번째 삼각형 변을 공유하기 시작한다.
즉, 규칙은 다음과 같다.

• dp[0] = dp[1] = dp[2] = 1
• dp[3] = dp[4] = 2
• dp[i] = dp [i-1] + dp[i-5]

코드

import java.util.Scanner;

public class ANS9461 {

    static int N;
    static long[] dp;

    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        //dp선언 및 초기화
        for(int i = 0 ; i < N; i++){
            int num = sc.nextInt();

            dp = new long[num+4];

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

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

    }
}

---