[백준] 9461 파도반 수열 - Dynamic Programming / Java

• 문제 링크

9461번: 파도반 수열

 

• 풀이 과정

문제에서 주어진 파도반 수열 p(1) ~ p(10) 의 변의 길이는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 이다.

 

이때 n < 6 까지는 불규칙한 수열이므로 미리 값을 메모이제이션해주고,

그 이후부터는 점화식 dp[i] = dp[i -1] + dp[i - 5] 이 성립하는 규칙성을 지니고 있다.

 

따라서 n 의 범위가 1 <= n < 100 으로 작은 수준이므로 미리 파도판 수열의 값을 구해 메모이제이션한 후,

테스트 케이스 당 입력 n 에 해당하는 dp(n) 을 정답으로써 출력한다.

 

• 풀이 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        long[] dp = new long[101];

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

        for (int i = 6; i <= 100; i++)
            dp[i] = dp[i - 1] + dp[i - 5];

        int t = Integer.parseInt(br.readLine());

        while (t-- > 0)
            bw.write(dp[Integer.parseInt(br.readLine())] + "\n");

        bw.flush();
    }

}