[2294] 동전 2

문제 링크 : https://www.acmicpc.net/problem/2294

2294 - 동전 2

본문

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

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

입력

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

출력

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

제한

시간 제한	메모리 제한
1sec	128MB

---

풀이

이전 문제와 상황은 똑같다. 이전 문제는 2293 - 동전 1 문제이다.

이전 문제와 상황이 약간 다르다. 이전에는 경우의 수를 세는 것이었지만, 이번에는 ‘만들 수 있다면 동전의 개수를 최소화’하는 문제다.

사실 방법은 똑같다. 일단 경우의 수를 찾아야하니까 기존 dp처럼 진행한다. 다만 이번에 저장할 값은 경우의 수가 아니라 그 경우를 만들 수 있는 동전의 개수 중 최솟값이다. 같은 수식으로도 풀어낼 수 있는 문제.

• 참고 알고리즘 : 다이나믹 프로그래밍

코드

사용 언어 : C

최종 수정일 : 2023 / 3 / 30

#include <stdio.h>

#define min(a, b) (((a) > (b)) ? (b) : (a))

int main() {
    int n, k;
    scanf("%d %d", &n, &k);

#define INF 987654321
#define MAX_IDX 10001
    int dp[MAX_IDX] = {0};
    for (int i = 1; i < MAX_IDX; ++i) {
        dp[i] = INF;
    }
    dp[0] = 0;

    for (int i = 0; i < n; ++i) {
        int a;
        scanf("%d", &a);
        for (int j = a; j <= k; ++j) {
            dp[j] = min(dp[j], dp[j - a] + 1);
        }
    }

    if (dp[k] == INF) {
        printf("-1");
    } else {
        printf("%d", dp[k]);
    }
    return 0;
}