백준 19947번 투자의 귀재 배주형 Java

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

문제

---

생각하기

---

• DP 문제이다.

• BFS로도 풀이가 가능하다.

동작

결과

코드

---

BFS

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

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, M;

    private static class Finance {
        int money;
        int option;
        int year;

        private Finance(int money, int option, int year) {
            this.money = money;
            this.option = option;
            this.year = year;
        }
    } // End of Finance class

    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(BFS());
        return sb.toString();
    } // End of solve()

    private static int BFS() {
        ArrayDeque<Finance> que = new ArrayDeque<>();
        que.offer(new Finance(N, 0, 0));
        int[][] memo = new int[M + 1][4];
        for (int i = 0; i <= M; i++) {
            Arrays.fill(memo[i], -1);
        }
        int ans = N;

        while (!que.isEmpty()) {
            Finance cur = que.poll();

            if (cur.year == M) {
                ans = Math.max(ans, cur.money);
                continue;
            }
            if (memo[cur.year][cur.option] != -1) continue;
            memo[cur.year][cur.option] = cur.money;


            // 1번 투자
            que.offer(new Finance((int) (cur.money * 1.05), 1, cur.year + 1));

            // 2번 투자
            if (cur.year + 3 <= M) {
                que.offer(new Finance((int) (cur.money * 1.2), 2, cur.year + 3));
            }

            if (cur.year + 5 <= M) {
                que.offer(new Finance((int) (cur.money * 1.35), 3, cur.year + 5));
            }
        }


        return ans;
    } // End of BFS()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
    } // End of input()
} // End of Main class

---

TopDown

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

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, M;
    private static int[] memo;
    private static final int INF = -1;

    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(M, N));
        return sb.toString();
    } // End of solve()

    private static int topDown(int year, int money) {
        if (year == 0) return money;

        if (memo[year] != INF) return memo[year];

        // 첫 번째 상품
        int ret = 0;
        ret = Math.max(ret, (int) (topDown(year - 1, money) * 1.05));

        // 두 번째 상품
        if (year - 3 >= 0) {
            ret = Math.max(ret, (int) (topDown(year - 3, money) * 1.2));
        }

        // 세 번째 상품
        if (year - 5 >= 0) {
            ret = Math.max(ret, (int) (topDown(year - 5, money) * 1.35));
        }


        return memo[year] = ret;
    } // End of topDown()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        memo = new int[M + 1];
        Arrays.fill(memo, INF);
    } // End of input()
} // End of Main class

---

BottomUp

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

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, M;
    private static int[] memo;
    private static final int INF = -1;

    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(M, N));
        return sb.toString();
    } // End of solve()

    private static int topDown(int year, int money) {
        if (year == 0) return money;

        if (memo[year] != INF) return memo[year];

        // 첫 번째 상품
        int ret = 0;
        ret = Math.max(ret, (int) (topDown(year - 1, money) * 1.05));

        // 두 번째 상품
        if (year - 3 >= 0) {
            ret = Math.max(ret, (int) (topDown(year - 3, money) * 1.2));
        }

        // 세 번째 상품
        if (year - 5 >= 0) {
            ret = Math.max(ret, (int) (topDown(year - 5, money) * 1.35));
        }


        return memo[year] = ret;
    } // End of topDown()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        memo = new int[M + 1];
        Arrays.fill(memo, INF);
    } // End of input()
} // End of Main class