[BOJ] 2294 동전 2 - JAVA

1. 문제

2294번: 동전 2

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

---

2. 풀이

1.  DP를 이용했다. K+1칸 배열을 만들어서 최소값을 저장한다.

2.  한 동전을 여러 번 사용할 수 있으므로 dp[k]는 최대 10000이다. (동전 최소값 1원 * K의 최대값 10000원) 따라서 dp를 10001로 초기화한다.

3.  0원을 만드는 경우는 없다. dp[0]에 0을 저장하고 탐색을 시작한다.

4.  동전 하나씩 보면서, 동전값부터 K까지 탐색한다. dp[i] = min(dp[i], dp[i-동전값]+1)이다. for문의 조건이 i<=K이기 때문에 동전 하나의 값이 K보다 큰 경우에도 여기서 걸러진다.

5.  dp를 초기화한 값(10001)보다 dp[K]가 작다면 출력하고, 그 외는 K원을 만들 수 없는 경우이므로 -1을 출력한다.

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

public class BOJ_2294_동전2 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.readLine());
      int N = Integer.parseInt(st.nextToken());
      int K = Integer.parseInt(st.nextToken());

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

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

      for(int coin:coins){
         for(int i=coin;i<=K;i++) dp[i] = Math.min(dp[i], dp[i-coin]+1);
      }

      if(dp[K] < 10001) System.out.println(dp[K]);
      else System.out.println(-1);
   }
}

---

3. 결과

1.  동전은 K보다 클 수 있다.

2.  한 동전을 여러 번 사용할 수 있으므로 dp[k]는 최대 10000이다. (동전 최소값 1원 * K의 최대값 10000원) 따라서 dp를 10001로 초기화해야한다.