[백준] 9461번 : 파도반 수열 (JAVA)

1. 문제 분석

 

점화식이 비교적 바로 떠오른 DP문제이다. 역시 DP문제는 점화식만 떠오르면 코드도 간결하고 쉬운거 같다.

 

시간복잡도 : O(N) 

알고리즘 : DP

2. 문제 풀이

P(1)부터 P(5)까지는 규칙이 없다. 그 이후에는 N번째 삼각형은 N-1번째와 N-5번째의 삼각형 변을 더한 값을 가진다.

• • dp[i] = dp[i-1] + dp[i-5]

 

3. 코드 구현

import java.util.Scanner;

public class BOJ_9461 {

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        long[] P = new long[101];
        P[1] = 1;
        P[2] = 1;
        P[3] = 1;
        P[4] = 2;
        P[5] = 2;


        for(int i = 0; i < T; i++){
            int N = sc.nextInt();

            for(int k = 6; k <= N; k++){
                P[k] = P[k-1] + P[k-5];
            }
            System.out.println(P[N]);
        }
        sc.close();
    }
}