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

[문제 링크]

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

[난이도]

- Silver 3

 

[알고리즘]

- DP

 

[코드]

import java.io.*;
import java.util.StringTokenizer;

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

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

            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 - 1] + dp[j - 5];
            }
            System.out.println(dp[n]);
        }

        /**
         * dp[1] = 1
         * dp[2] = 1
         * dp[3] = 1
         * dp[4] = 2
         * dp[5] = 2
         * dp[6] = 3 = dp[5] + dp[1]
         * dp[7] = 4 = dp[6] + dp[2]
         * dp[8] = 5 = dp[7] + dp[3]
         * dp[9] = 7 = dp[8] + dp[4]
         * dp[10] = 9 = dp[9] + dp[5]
         * dp[11] = 12 = dp[10] + dp[6]
         * dp[12] = 16 = dp[11] + dp[7]
         *
         * dp[n] = dp[n-1] + dp[n-5]
         */

    }
}

[풀이]

1. dp 배열 정의

dp[1] = 1
dp[2] = 1
dp[3] = 1
dp[4] = 2
dp[5] = 2
dp[6] = 3 = dp[5] + dp[1]
dp[7] = 4 = dp[6] + dp[2]
dp[8] = 5 = dp[7] + dp[3]
dp[9] = 7 = dp[8] + dp[4]
dp[10] = 9 = dp[9] + dp[5]
dp[11] = 12 = dp[10] + dp[6]
dp[12] = 16 = dp[11] + dp[7]

 

2. 초기값 설정

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

 

3. 점화식 작성

dp[n] = dp[n-1] + dp[n-5]