[백준] Gold V. 동전 2

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

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초 (추가 시간 없음)

128 MB

75632

23336

16612

29.902%

문제

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

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

출력

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

 

사용 알고리즘

• 다이나믹 프로그래밍

 

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

/*
    테이블: d[i]: 합이 i일때 만들 수 있는 동전의 최소 개수
    점화식: d[i] =
 */
public class Main {
    static int n, k;
    static int min = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        int [] coins = new int[n];
        int[] d = new int[k + 1];
        for(int i = 0; i < n; i++) {
            coins[i] = Integer.parseInt(br.readLine());
        }

        Arrays.fill(d, Integer.MAX_VALUE);
        d[0] = 0;
        for(int coin : coins) {
            for(int i = coin; i <= k; i++){
                if (d[i-coin] != Integer.MAX_VALUE)
                    d[i] = Math.min(d[i], d[i-coin] + 1);
            }

        }
        if (d[k] == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(d[k]);
        }
    }
}

 

 

회고

 

이전 동전 문제에서는, 합이 k일때 만들 수 있는 모든 경우의 수를 구해야 했다면 이 문제는 합이 k일때의 최소 동전의 개수를 구하는 문제였다.

 

3 15
1
5
12

 

동전이 (1,5,12)가 주어지고 합이 15를 만든다고 가정하자.

 

1로만 동전을 만드는 경우의 수: 1,2, ... 15

5로만 동전을 만드는 경우의 수: (5부터 시작) 1, 2 ,. ... 3

12로만 동전을 만드는 경우의 수: (12부터 시작) 1, .... 4 (dp[12] + dp[3])

 

d[k] 값이 각각 15, 3, 4가 나오는데 여기서 최솟값을 구해주면 되는 문제였다.

 

여기까지는 접근을 잘 했는데, 최솟값을 구하는 과정에서 좀 애를 먹었다.

d[i] = Math.min(d[i], d[i-coin] + 1);

 

이렇게 식을 세웠는데, 처음에 d[i] 값들을 MAX로 초기화 해주지 않아서 전부 0이 출력되어서 헷갈렸었다. min을 구할때는

꼭!!! 초기화를 MAX값으로 해두자.

 

그리고, 최솟값을 갱신할 때 이 조건을 꼭 붙이자.

if (d[i-coin] != Integer.MAX_VALUE)

 

나는 d[i] != Integer.MAX_VALUE로 잘못 조건을 설정했었다.

 

if (d[k] == Integer.MAX_VALUE) {
    System.out.println(-1);
} else {
    System.out.println(d[k]);
}

 

마지막에, 해당 코인을 만들 수 없는 경우는 -1, 만들 수 있다면 갱신된 최솟값을 출력해주면 된다.