(Java) 백준 9095 - 1, 2, 3 더하기

문제 유형부터 DP를 이용하라고 나와 있었다.
저번처럼 Top-down 방식과 Bottom-up 방식 모두를 생각해서 풀었다.
나는 Top-down 방식이 먼저 떠올랐고 재귀를 통해 성공했다.
오히려 점화식을 도출해야 풀 수 있는 Bottom-up 방식이 더 어려웠다.
Top-down 방식은 n의 조건이
최대 10이기 때문에 성공한 것 같다.
아마 n의 크기가 컸다면 재귀 호출이 많아져서
시간 초과가 났을것 같다.
Bottom-up 방식에서는 동적으로 배열의 크기를 설정했는데 런타임 에러가 나서
초기값을 11로 고정해서 풀었다.

---

Top-down 방식 코드

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

public class Main {
    static int answer = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        int[] n = new int[t];
        for (int i = 0; i < t; i++) {
            n[i] = Integer.parseInt(br.readLine());
        }
        // top-down 방식
        for (int i : n) {
            topDown(i);
            System.out.println(answer);
            answer = 0;
        }
    }

    static void topDown(int num) {
        // 재귀 탈출조건
        if (num == 0) {
            answer++;
            return;
        }
        // 1뺴기
        if (num - 1 >= 0) {
            topDown(num - 1);
        }
        // 2빼기
        if (num - 2 >= 0) {
            topDown(num - 2);
        }
        // 3빼기
        if (num - 3 >= 0) {
            topDown(num - 3);
        }
    }
}

Bottom-up 방식 코드

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

public class Main {
    static int answer = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        int[] n = new int[t];
        for (int i = 0; i < t; i++) {
            n[i] = Integer.parseInt(br.readLine());
        }
        // bottom-up 방식
        for (int i : n) {
            bottomUp(i);
            System.out.println(answer);
            answer = 0;
        }
    }

    static void bottomUp(int num) {
//        int[] dp = new int[num + 1]; 런타임 에러
        int[] dp = new int[11];
        // 1을 만드는 방법의 수
        dp[1] = 1;
        // 2를 만드는 방법의 수
        dp[2] = 2;
        // 3을 만드는 방법의 수
        dp[3] = 4;
        for (int i = 4; i < num + 1; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }
        answer = dp[num];
    }
}