[백준][DP] 2294번 : 동전 2 문제

동전 2 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	8781	2028	1361	24.629%

문제

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

입력

첫째줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다.

출력

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

예제 입력 

3 15
1
5
12

예제 출력 

3

힌트

출처

• 잘못된 조건을 찾은 사람: apples1309
• 데이터를 추가한 사람: isac322

알고리즘 분류

• 다이나믹 프로그래밍
• 동전 교환

소스)

  
#include<iostream>
 
 
int main() {
 
    //input coin_num 코인의 수, coin_total 구하려는 코인 값
 
    int coin_num;
    int coin_total;
 
    //코인
    int coins[100];
    
 
    //각 코인의 횟수 
    int min_coins_num[10001];
 
    std::cin >> coin_num >> coin_total;
    
    for (int i = 0; i < coin_num; i++) {
        std::cin >> coins[i];
    }
 
    min_coins_num[0] = 0;
 
    // 첫번째 코인부터 구하려는 코인값까지 dp
    for (int i = 1; i <= coin_total; i++) {
        
        int min = 10001; // 최대 나올수 있는 최악의 코인의 수는 10000
        for (int j = 0; j < coin_num; j++) {
            if (i - coins[j] < 0) continue;        // 음수 일 경우 계산 될 수 없는 부분이다.
            else{
                if (min_coins_num[i - coins[j]] < 0) continue;    // 전 코인을 참조 할 때 -1 이 있으면 그 수는 계산 불가능이다.
                if (min_coins_num[i - coins[j]] + 1 < min) {    // 가능할경우 최소의 수 비교
                    min = min_coins_num[i - coins[j]] + 1;
                }
            }
        }
        if(min < 10001)
            min_coins_num[i] = min;
        else
            min_coins_num[i] = -1;    //불가할경우 -1 
    }
 
    std::cout << min_coins_num[coin_total] << std::endl;
    return -1;
}