[백준] 9461번:파도반 수열 (Java 자바)

문제

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

9461번: 파도반 수열

 

풀이 및 소스코드

 

dp[n] = dp[n-2]+dp[n-3] 이라는 규칙이 있다.

n이 100까지이므로 dp 배열은 long으로 해줘야 한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main {
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		long[] dp = new long[101];
		dp[1] = 1;
		dp[2] = 1;
		dp[3] = 1;
		int cnt = 3;
		int t = Integer.parseInt(br.readLine());
		for(int tt=0;tt<t;tt++) {
			int n = Integer.parseInt(br.readLine());
			if(n<=cnt) {
				sb.append(dp[n]).append("\n");
				continue;
			}
			
			for(int i=cnt+1;i<=n;i++) {
				dp[i] = dp[i-2]+dp[i-3];
			}
			sb.append(dp[n]).append("\n");
		}
		System.out.println(sb);
	}
	
}