[백준 9461] 파도반 수열

 

피보나치 수열과 비슷한 규칙을 가진 수열이다.

 

수열을 잘 살펴보면

dp[i] = dp[i-3] + dp[i-2]

와 같은 점화식을 얻을 수 있다.

 

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