파도반 수열이라는 문제이다.

예시가 p(1) 부터 p(10) 까지 주어져있는 것을 보고

다음과 같은 규칙을 찾을 찾아서 

Dynamic Programming 을 통해 해결하였다.

p(4) = p(3) + p(2) 👉 2 = 1 + 1

p(5) = p(4) + p(3) 👉 2 = 1 + 1

p(6) = p(5) + p(4) 👉 3 = 2 + 1
        .
        .
        .
p(n) = p(n-3) + p(n-2)

package problem.dynamic.Q9461;
import java.io.*;

public class Main_9461 {
    public static int n;
    public static long[] d = new long[101];

    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int input[] = input();
        solve();
        for (int i = 1; i <= n; i++) {
            bw.write(Long.toString(d[input[i]]));
            bw.write("\n");
        }
        bw.flush();
        bw.close();
    }

    public static void solve() {
        for (int i = 1; i <= 100; i++) {
            if (i < 4) {
                d[i] = 1;
                continue;
            }
            d[i] = d[i - 3] + d[i - 2];
        }
    }

    public static int[] input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        int numbers[] = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            numbers[i] = Integer.parseInt(br.readLine());
        }
        br.close();
        return numbers;
    }
}