백준 9461번 : 파도반 수열(Java)

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

9461번: 파도반 수열

---

[풀이]

 

- 다이나믹 프로그래밍 유형의 문제입니다.
- 피보나치 수열의 식을 기억하시나요? 피보나치 수열의 식처럼 비슷한 점화식을 구현할 수 있습니다.(저도 규칙을 찾는게 쉽지는 않았습니다.)
- dp[n] = dp[n-2] + dp[n-3]의 식을 구현하면 됩니다.
- 최대 n의 값은 100이므로 dp 배열의 크기는 101로 선언하여 값을 할당했습니다.
- 테스트 케이스 횟수만큼 dp 배열에서 각 값을 출력합니다.

 

---

[코드]

 

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));
		int t = Integer.parseInt(br.readLine());
		long[] dp = new long[101];
		dp[0] = 0;
		dp[1] = 1;
		dp[2] = 1;
		dp[3] = 1;
		
		for(int i = 4; i< 101; i++){
			dp[i] = dp[i-2] + dp[i-3];
		}
		
		while(t-- > 0){
			int n = Integer.parseInt(br.readLine());
			System.out.println(dp[n]);
		}
	}
}