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

DP알고리즘 문제로 규칙을 찾으면 쉽게 풀 수 있는 문제다.

1차원 배열을 선언해주고 index 4까지는 입력을 해준다

index 5부터는 알고리즘을 작성해서 입력한다.

 

규칙

P(N) = P(N-5) + P(N-1)

 

단, 배열을 int로 선언 할 경우, 범위를 초과해서 -값이 입력된다.

이를 방지하기위해 가장 큰 정수형 타입인 long으로 배열을 선언한다.

 

package codingTest_backjoon;

import java.util.Scanner;

//파도반수열
public class Main_9461 {
	
	public static void main(String[] args) {
		
		Scanner scan = new Scanner(System.in);
		
		int num = scan.nextInt();
		
		for(int r=0; r<num; r++) {
			int N = scan.nextInt();
			
			if(N <= 5) {
				long[] arg = new long[5];
				arg[0] = 1; arg[1] = 1; arg[2] = 1; arg[3] = 2; arg[4] = 2;
				System.out.println(arg[N-1]);
			}else {
				long[] arg = new long[N];
				arg[0] = 1; arg[1] = 1; arg[2] = 1; arg[3] = 2; arg[4] = 2;
				for(int i=5; i<N; i++) {
					arg[i] = arg[i-5] + arg[i-1];
				}
				System.out.println(arg[N-1]);
			}
		}
	}

}