백준 9461 파도반 수열 JAVA (DP)

1. 문제

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

9461번: 파도반 수열

 

2. 설명

점화식이 dp[n] = dp[n-1] + dp[n-5] 였다.

또한 n의 범위가 100까지이기 때문에 int형으로 dp를 선언하면 틀렸다고 나온다.

이부분은 항상 헷갈린당;

 

3. 코드

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

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int T = Integer.parseInt(st.nextToken());
		int[] n = new int[T];
		long[] dp = new long[101];
		
		for(int i=0; i<T; i++) {
			st = new StringTokenizer(br.readLine());
			n[i] = Integer.parseInt(st.nextToken());
		}
		
		dp[1] = 1;
		dp[2] = 1;
		dp[3] = 1;
		dp[4] = 2;
		
		for(int i=0; i<T; i++) {
			for(int j=5; j<=n[i]; j++) {
				dp[j] = dp[j-1] + dp[j-5];
			}
			System.out.println(dp[n[i]]);
		}
	}
}