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

📎 문제 출처

---

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

📌 문제 설명

---

❓ 풀이 방법

---

p(n)의 규칙을 찾았다.
1 1 1 2 2 3 4 5 7 9 12 16 21 ...
p(n) = p(n-2) + p(n-3)이다.

처음에 dp테이블을 int로 풀었더니 n이 커지니까 음수가 나왔다. 수가 너무 커져서 int형의 범위를 벗어나서 그렇다. 그래서 dp테이블을 long으로 선언했다.

📌 Code1 top-down

---

package com.ll;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static long[] dp;

    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());
            dp = new long[n+1];
            System.out.println(p(n));
        }
    }

    public static long p(int n) {
        if(n <= 3) return dp[n] = 1;
        if(dp[n] != 0) return dp[n];
        return dp[n] = p(n-2) + p(n-3);
    }

}

📌 Code2 bottom-up

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static long[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        dp = new long[101];

        for(int i = 1; i <= 100; i++) {
            if(i <= 3) dp[i] = 1;
            else dp[i] = dp[i-2] + dp[i-3];
        }

        for(int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());
            System.out.println(dp[N]);
        }

    }


}