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

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

9461번: 파도반 수열

규칙만 찾으면 쉽게 풀 수 있는 문제이다.

P(1)부터 P(10)까지의 값은 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

여기서 내가 발견한 규칙은 각 n자리의 값을 dp [n]이라고 했을 때 dp[n]= dp[n-3] + dp[n-2]이다.

배열은 0부터 시작이므로 dp[0]=0으로 초기화시켜주고 dp[1]=1,dp[2]=1로 초기화 시키면 n>=3부터 적용시킬 수 있다. 

 

또 다른 두번째 규칙은 dp[n]= dp[n-5] + dp[n-1] 이다.

이 규칙을 적용시키기 위해 dp[0]=0, dp[1]=1,dp[2]=1, dp[3]=1,dp[4]=2, dp[5]=2로 초기화만 잘 시켜주면 된다.

 

주의할 점!

dp [] 배열은 크기가 100까지 값을 저장해야 하므로 자료형이 int가 아니라 long이어야 한다. 주의하자

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		
		Scanner s= new Scanner(System.in);
		
		int T= s.nextInt();
		
		long  dp[] = new long [101];
	
		
		dp[0]=0;
		dp[1]=1;
		dp[2]=1;
	
		
		for(int i=3;i<101;i++) {
			dp[i]= dp[i-3]+dp[i-2];
		}
		
		
		for(int i=0;i<T;i++) {
			int n = s.nextInt();
			System.out.println(dp[n]);
			
		}
	
		
	}
	
}