백준 9461 : 파도반 수열 _자바 Java

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

9461번: 파도반 수열

---

1) 규칙찾기!

N	1	2	3	4	5	6	7	8	9
p(N)	1	1	1	2	2	3	4	5	7

가정 1. p(N) = p(N-1)+p(N-2) 일 것이다?

p(4)=p(3)+p(2)=2 (O)

p(5)=p(4)+p(3)=3 (X)  틀림.

 

가정 2. p(N) = p(N-2)+p(N-3) 일 것이다?

p(5)=p(2)+p(1)=2 (O)

p(6)=p(4)+p(3)=3 (O)

p(7)=p(5)+p(4)=4 (O)

p(8)=p(6)+p(5)=5 (O)

p(9)=p(7)+p(6)=7 (O)   맞음.

 

---

 

import java.io.*;
import java.util.*;

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;
		
		for(int i=3;i<101;i++) {
			dp[i]=dp[i-3]+dp[i-2];
		}
		
		for(int i=0;i<T;i++) {
			int num=Integer.parseInt(br.readLine());
			System.out.println(dp[num]);
		}
	}
	

}