백준 24416번
https://www.acmicpc.net/problem/24416

문제

---

생각하기

---

• DP, TopDown, BottomUp 문제이다.

동작

TopDown을 통해서 값을 미리 구한다.

Bottom Up 같은 경우는 기저 조건으로 memo[1] = 1, memo[2] = 1을 미리 줬기 때문에

1, 2을 제외하고 3부터 시작해서 3 ~ N 까지 계산하기 때문에

N - 2를 하면 된다.

결과

코드

---

import java.io.*;
import java.util.Arrays;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N;
    private static int[] memo;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        sb.append(topDown(N)).append(' ');
        sb.append(N - 2);

        return sb.toString();
    } // End of solve()

    private static int topDown(int n) {
        if (n <= 1) return n;

        if (memo[n] != -1) return memo[n];

        memo[n] = topDown(n - 1) + topDown(n - 2);
        return memo[n];
    } // End of topDown();

    private static void input() throws IOException {
        N = Integer.parseInt(br.readLine());
        memo = new int[N + 1];
        Arrays.fill(memo, -1);
    } // End of input()
} // End of Main class