파도반 수열

문제 정보

• 백준 실버 3
• DP
• 문제 링크

풀이

수열 값을 보면 다음과 같다.

• P(1) = P(2) = P(3) = 1
• P(4) = P(5) = 2
• P(6) = 3
• P(7) = 4
• P(8) = 5
• P(9) = 7
• P(10) = 9
• P(11) = 12
• P(12) = 16
• P(13) = 21
• P(14) = 28
• …

여기서 P(6) = P(5) + P(1), P(7) = P(6) + P(2), … 로, 점화식은 P(i) = P(i - 1) + P(i - 5) 임을 알 수 있다. 꼭 수열 값이 아니더라도, 그림을 통해서도 알 수 있다.

하나 주의해야 하는 점은 int 배열을 사용할 경우 오버플로우가 발생하기 때문에 long 배열을 사용해야 한다.

코드

import java.io.*;
import java.util.*;
 
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());
        
        long[] dp = new long[101];
        dp[1] = dp[2] = dp[3] = 1;
        dp[4] = dp[5] = 2;
        
        int idx = 6;
        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            
            for (;idx <= n; idx++)
                dp[idx] = dp[idx - 1] + dp[idx - 5];
            
            System.out.println(dp[n]);
        }
    }
}