백준 11047 - 동전0

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

11047번: 동전 0

문제 설명

---

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

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

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

 

 

접근 방식

---

동전의 개수가 최소가 되기 위해서는 가장 가치가 큰 동전을 많이 가지고 있을수록 개수가 최소가 됩니다. 그래서 그리디 알고리즘 방식을 이용하면 손쉽게 해결 가능합니다~

 

 

코드

---

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int n,k;
int main(){
    cin>>n>>k;
    int coin[n];
    int num=0;
    for(int i=0;i<n;i++) cin>>coin[i];
    for(int i=n-1;i>=0;i--){
        if((k/coin[i])==0) continue;
        num += (k/coin[i]);
        k = k%coin[i];
        if(k==0) break;   
        
    }
    cout<<num<<"\n";
}

funny algorithm *0*~