[백준] 2294번 - 동전 2 [Java]

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

 

[백준] 2294번 - 동전 2 [Java]

---

1.  아이디어

 

무한 배낭 문제로 다이나믹 프로그래밍을 활용해서 해결할 수 있다.

---

2. 문제풀이

 

각 가치를 만드는데 필요한 동전의 최소 개수를 저장하는 문제로 역시 주어지는 동전의 종류가 늘어난다고 생각하는 배낭 스타일로 풀 수 있다. dp 테이블의 초기화가 중요한데 0원을 만드는데는 동전이 필요없으니 0개이고 나머지 금액을 만드는데는 동전이 무한히 많이 필요하다고 초기화를 해줘서 이후 갱신과정에서 최소 개수로 갱신이 되도록 해줘야 한다.

---

3. 코드

 

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

public class Main_1D {

    private static final int MAX = 10001;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

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

        int[] dp = new int[1 + K];
        for (int i = 1; i <= K; i++) {
            dp[i] = MAX;
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= K; j++) {
                if (j >= coins[i]) dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
            }
        }

        System.out.println(dp[K] == MAX ? -1 : dp[K]);
    }
}

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

public class Main_2D {

    private static final int MAX = 10001;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

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

        int[][] dp = new int[1 + N][1 + K];
        Arrays.fill(dp[0], MAX);

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= K; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= coins[i]) dp[i][j] = Math.min(dp[i][j], dp[i][j - coins[i]] + 1);
            }
        }

        System.out.println(dp[N][K] == MAX ? -1 : dp[N][K]);
    }
}

---

4. 후기

 

- 1차원 dp

- 2차원 dp