[백준 자바JAVA] 9461번 - 파도반 수열

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

---

● 문제

일반적인 dp문제이다. 문제에서 주어진 첫 10개의 숫자 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, ... 을 보면 dp[N] = dp[N - 3] + dp[N - 2]라는 공식이 나오게 된다.

다만 파도반 수열은 100의 경우 900억이 넘기 때문에 long형태로 배열에 저장해야한다.

---

● 코드

import java.io.*;

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());

        for(int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());
            long[] dp = new long[1001];

            dp[0] = 1;
            dp[1] = 1;
            dp[2] = 1;

            for(int j = 3; j <= N; j++) {
                dp[j] = dp[j - 3] + dp[j - 2];
            }

            System.out.println(dp[N - 1]);
        }
    }
}