백준 22115번 창영이와 커피 Java

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

문제

---

생각하기

---

• 배낭 문제이다.

동작

결과

코드

---

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, K;
    private static int[] arr;
    private static int[][] memo;
    private static final int MAX = 100_101;

    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();

        // 정확히 K카페인
        int ans = topDown(N, K);
        if (ans == MAX) {
            sb.append(-1);
        } else {
            sb.append(ans);
        }

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

    private static int topDown(int n, int k) {
        if (k == 0) return 0;
        if (n == 0) return MAX;

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

        int result = topDown(n - 1, k);
        if (k >= arr[n - 1]) {
            int cur = topDown(n - 1, k - arr[n - 1]);
            if (cur != MAX) {
                result = Math.min(result, cur + 1);
            }
        }

        memo[n][k] = result;
        return memo[n][k];
    } // End of topDown()

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

        arr = new int[N];
        memo = new int[N + 1][K + 1];
        for (int i = 0; i <= N; i++) {
            Arrays.fill(memo[i], -1);
        }
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
    } // 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, K;
    private static int[] arr, memo;
    private static final int MAX = 100_101;

    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();

        memo[0] = 0;
        for (int i = 0; i < N; i++) {
            for (int j = K; j >= 0; j--) {
                if (j - arr[i] >= 0 && memo[j - arr[i]] != MAX) {
                    memo[j] = Math.min(memo[j], memo[j - arr[i]] + 1);
                }
            }
        }
        
        sb.append(memo[K] == MAX ? -1 : memo[K]);
        return sb.toString();
    } // End of solve()

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

        arr = new int[N];
        memo = new int[K + 1];
        Arrays.fill(memo, MAX);
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
    } // End of input()
} // End of Main class