[백준_JAVA_알고리즘] 9461 파도반 수열 #DP

해당 문제는 DP를 이용해서 풀 수 있습니다.

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(bufferedReader.readLine());

        for(int i = 0; i < T; i++){
            int N = Integer.parseInt(bufferedReader.readLine());
            long[] dp = new long[N + 1];

            dp[0] = 0L;
            if(N > 0) dp[1] = 1L;
            if(N > 1) dp[2] = 1L;

            /*
                dp[3] = 2;
                dp[4] = 2;
                dp[5] = 3;
                dp[6] = 4;
                dp[7] = 5;
            */

            for(int j = 3; j <= N; j++){
                dp[j] = dp[j-3] + dp[j-2];
            }
            System.out.println(dp[N]);
        }
    }
}

 

dp[j] = dp[j-3] + dp[j-2] 점화식 계산 과정에서 결과 값이 빠르게 증가할 수 있으므로 Long형으로 지정합니다.

dp[0] 부터 예상되는 값을 나열하면 규칙을 찾을 수 있습니다.

점화식을 생각하는 것이 문제의 핵심입니다.

 

.

.

.

 

문제는 아래에서 확인할 수 있습니다.

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