September 28, 2021

문제

N가지 종류의 화폐가 있습니다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 합니다. 이때 각 종류의 화폐는 몇 개라도 사용할 수 있습니다.

예를 들어, 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 최소한의 화폐 개수입니다.

M원을 만들기 위한 최소한의 화폐 개수를 출력하는 프로그램을 작성하세요.

시간 제한

1초

메모리 제한

128MB

입력 조건

첫째 줄에 N, M이 주어진다.(1≤N≤100, 1≤M≤10,000)

이후 N개의 줄에는 각 화폐의 가치가 주어진다. 화폐의 가치는 10,000보다 작거나 같은 자연수이다.

출력 조건

첫째 줄에 최소 화폐 개수를 출력한다.

불가능할 때는 -1을 출력한다.

풀이

#include <stdio.h>

using namespace std;

int N, M, tmp;
int price[100], dp[10001];

void makeBill() {
    for (int i = 1; i <= M; ++i) {
        for (int j = 0; j < N; ++j) {
            if (i - price[j] > 0 && dp[i - price[j]] != 0) {
                tmp = dp[i - price[j]] + 1;

                if (dp[i] == 0 || dp[i] > tmp) {
                    dp[i] = tmp;
                }
            }
        }
    }
}

int main() {
    scanf("%d %d", &N, &M);

    for (int i = 0; i < N; ++i) {
        scanf("%d", &tmp);

        price[i] = tmp;
        dp[tmp] = 1;
    }
    
    makeBill();

    tmp = dp[M] == 0 ? -1 : dp[M];

    printf("%d", tmp);

    return 0;
}

가치가 k인 동전에 대해서 dp[i]는 다음과 같다.