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

문제

---

생각하기

---

• 배낭 문제이다.

• TopDown -> 메모이제이션을 활용

• BottomUp -> 중복계산을 제거

동작

결과

코드

---

TopDown

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

public class Main {

    // input
    private static BufferedReader br;

    // variables

    private static final int MOD = 10007;
    private static int N, M, H;
    private static int[][] arr, 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();

        // 사용할 수 있는 블럭은 최대 M개지만 선택지는 최대 M + 1개가 된다.
        sb.append(topDown(N, H));
        return sb.toString();
    } // End of solve()

    private static int topDown(int n, int h) {
        if (h == 0) return 1;
        if (n == 0) return 0;

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

        int ret = topDown(n - 1, h);
        for (int block : arr[n - 1]) {
            if (h >= block) {
                ret = (ret + topDown(n - 1, h - block)) % MOD;
            }
        }

        return memo[n][h] = 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());
        H = Integer.parseInt(st.nextToken());

        arr = new int[N][];
        for (int i = 0; i < N; i++) {
            arr[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }

        memo = new int[N + 1][H + 1];
        for (int i = 0; i <= N; i++) {
            Arrays.fill(memo[i], -1);
        }
    } // End of input()
} // End of Main class

---

BottomUp

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

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static final int MOD = 10_007;
    private static int N, M, H;
    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() throws IOException {
        StringBuilder sb = new StringBuilder();

        memo = new int[N + 1][H + 1];
        memo[0][0] = 1; // base case

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

    private static int bottomUp() throws IOException {

        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int count = st.countTokens();
            memo[i - 1][0] = 1;

            for (int j = 0; j < count; j++) {
                int block = Integer.parseInt(st.nextToken());

                for (int k = block; k <= H; k++) {
                    memo[i][k] = (memo[i][k] + memo[i - 1][k - block]) % MOD;
                }
            }

            for (int j = 1; j <= H; j++) {
                memo[i][j] = (memo[i][j] + memo[i - 1][j]) % MOD;
            }
        }

        return memo[N][H];
    } // End of bottomUp()

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

    } // End of input()
} // End of Main class