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

문제

---

생각하기

---

• 배낭 문제, DP 문제 이다.

동작

• n = coinIndex, m = amount

• 최종적으로 0원을 만드는 방법 -> 더 이상 동전을 사용할 필요가 없는 경우) 하나의 유효한 조합으로 간주된다.

    private static int topDown(int n, int m) {
        if (m == 0) return 1;
        if (n <= 0 || m < 0) return 0; // 사용할 수 있는 동전이 없거나, 금액을 만들 수 없는 경우

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

        // 현재 선택된 동전을 사용하는 경우 + 사용하지 않는 경우
        memo[n][m] = topDown(n, m - coins[n - 1]) + topDown(n - 1, m);

        return memo[n][m];
    } // End of topDown()

        // 현재 선택된 동전을 사용하는 경우 + 사용하지 않는 경우
        memo[n][m] = topDown(n, m - coins[n - 1]) + topDown(n - 1, m);

• 동전을 사용한다고 했을 때, n이 감소 하지 않는 이유는 동전의 사용횟수가 정해져 있지 않기 때문에 같은 동전을 계속 사용하는 조건, 동전을 사용하지 않아서 다음으로 넘어가는 n - 1의 선택지가 있다.

결과

코드

---

Top Down

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 int[] coins;

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

        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            input();

            bw.write(solve());
        }

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

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

        sb.append(topDown(N, M)).append('\n');
        return sb.toString();
    } // End of solve()

    private static int topDown(int n, int m) {
        if (m == 0) return 1;
        if (n <= 0 || m < 0) return 0; // 사용할 수 있는 동전이 없거나, 금액을 만들 수 없는 경우

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

        // 현재 선택된 동전을 사용하는 경우 + 사용하지 않는 경우
        memo[n][m] = topDown(n, m - coins[n - 1]) + topDown(n - 1, m);

        return memo[n][m];
    } // End of topDown()

    private static void input() throws IOException {
        N = Integer.parseInt(br.readLine());
        coins = new int[N + 1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            coins[i] = Integer.parseInt(st.nextToken());
        }

        M = Integer.parseInt(br.readLine());
        memo = new int[N + 1][M + 1];

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

Bottom Up

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 int[] coins;

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

        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            input();

            bw.write(solve());
        }

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

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

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

    private static int bottomUp() {
        // 기저조건
        for (int i = 0; i <= N; i++) {
            memo[i][0] = 1;
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                // 현재 동전의 가치가 j보다 크면, 이 동전은 사용할 수 없다.
                if (coins[i - 1] > j) {
                    memo[i][j] = memo[i - 1][j];
                } else {
                    // 현재 동전을 사용하지 않는 경우 + 현재 동전을 사용하는 경우
                    memo[i][j] = memo[i - 1][j] + memo[i][j - coins[i - 1]];
                }
            }
        }


        return memo[N][M];
    } // End of bottomUp


    private static void input() throws IOException {
        N = Integer.parseInt(br.readLine());
        coins = new int[N + 1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            coins[i] = Integer.parseInt(st.nextToken());
        }

        M = Integer.parseInt(br.readLine());
        memo = new int[N + 1][M + 1];
    } // End of input()
} // End of Main class