[JAVA] 백준 9461번 - 파도반 수열

 

📖 문제

 

📋 코드

import java.util.*;
public class Main {
	
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();
		long P[] = new long[101];
		
		P[1] = 1;
		P[2] = 1;
		P[3] = 1;
		P[4] = 2;
		P[5] = 2;
		
		for (int i = 6; i <= 100; i++) {
			P[i] = P[i-1] + P[i-5];
		}
		
		for (int i = 0; i < T; i++) {
			int N = sc.nextInt();
			System.out.println(P[N]);
		}
	}
}

👨🏻‍💻 결과

 

 

📕 풀이 방법

 

<기본 점화식>

DP[i] = DP[i-1] + DP[i-5];

 

배열 P의 자료형을 int로했을 때 P(79)부터 int형의 범위를 넘어서게 됩니다.

따라서 long으로 지정해줍시다.

 

 

🔗 링크

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

9461번: 파도반 수열