[백준,BOJ 9461] 파도반 수열(JAVA 구현)

 

-내 생각

  이제 동적 프로그래밍 알고리즘 분류의 문제를 4문제 째 풀고 있는데, 알 수 있었던 것은 무언가 수열과 같은 규칙이 발견되면 점화식을 세우는 것이 가장 중요한 것 같다. 또한 대다수의 수열은 수가 커질수록 기하급수적으로 수가 커지기 때문에 자료타입에 신경을 많이 써야 한다는 것이다. 이번 문제의 경우에도 점화식은 자세히 보면 dp[n] = dp [n-2] + dp [n-3]이라는 점화식을 찾을 수 있다. 또 한 가지 더 찾을 수 있는데 이 부분은 다른 분들의 글을 알 수 있었다. 

dp [n] = dp [n-1] + dp [n-5] 역시도 성립한다는 점이다. 필자는 첫 번째 점화식을 사용하였는데 오답 처리를 받아 검색해보다가 자료 타입에 문제가 있었다는 것을 알 수 있었다. int 형이 아닌 long형을 사용해야 한다.

 

-해법

import java.util.*;

public class Main {
	static int t,n;
	
	static long dp[]; // 메모이제이션

	
	public static void main(String[] args)   {
		Scanner sc = new Scanner(System.in);
		
		t=sc.nextInt();
		
		dp = new long[101];
		
		dp[1] =1; //초기 3개의 값 저장
		dp[2]=1;
		dp[3] =1;
		
		for(int i=0;i<t;i++) {
			n = sc.nextInt();
			
			for(int j=4;j<=n;j++) { //3개를 저장했으므로 4개부터 시작
				dp[j] = dp[j-2] + dp[j-3]; //점화식
			}
				
			System.out.println(dp[n]); //출력
			
		}
		
		
		
	}
	
}