11047 - 동전 0[S4]

문제

 

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

11047번: 동전 0

 

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

 

풀이

 

문제 유형이 그리디였으나, dp를 사용하였다.

그리디 형태로 푼다면 가장 높은 코인을 사용 후 나머지를 사용하여 풀 수 있을 것이다.

 

사실 이 풀이의 경우 완전히 내 것이 아니라 타 인원과의 레퍼런스를 통해서 얻은 결론이었는데 풀이 방법이 유니크하여 부가적으로 정리하였다.

 

2중 for문의 내부에서는 coins[i] (편의상 coin이라 한다)을 통해 이전 값과의 최소 동전 개수를 비교한다.

j = coin이므로, dp 배열이 0 미만으로 떨어지는 일은 없다.

어차피 코인의 개수는 + 1이 되므로, coin 값만큼 차이나는 이전 dp값의 count와 비교하여 최저 값을 갱신하는 방법이다.

 

 

코드

 

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

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N, K;
    static int[] dp;

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        dp = new int[K + 1];
        Arrays.fill(dp, Integer.MAX_VALUE); 

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

        dp[0] = 0; // 0원
        for (int i = 0; i < N; i++) {
            for (int j = coins[i]; j <= K; j++) { //K원보다 같거나 커질 때까지
                dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1); // coins[i] + 1개의 개수와 비교
            }
        }

        if (dp[K] == Integer.MAX_VALUE) { // 만들 수 없는 경우
            System.out.println(-1);
        } else {
            System.out.println(dp[K]);
        }
    }
}

 

 

그 외 그리디 사용

 

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

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N, K;
    
    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        Integer[] coins = new Integer[N];

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

        Arrays.sort(coins, Collections.reverseOrder()); // 내림차순 정렬
        int count = 0;
        for (int coin : coins) {
            if (K >= coin) {
                count += K / coin; // 해당 동전으로 만들 수 있는 최대 개수
                K %= coin; // 나머지 금액
            }
        }
        System.out.println(count);
    }
}