[백준] 파도반 수열

참고 : www.acmicpc.net/problem/9461

 

- dp 문제

- dp[i] : i번째 가ㄴㅇ장 긴 변의 길

(4번째 이후로 i-2번째와 i-3번째 가장 긴 변의 길이의 합과 같음 = 회전하므로 같은 규칙을 항상 가지게 된다.)

 

import java.util.Scanner;
import java.util.Stack;

public class Main {

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

    }
}