[문제]
준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.
동전을 적절히 사용해서 그 가치의 합을 k로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.
[입력]
첫째 줄에 N과 K가 주어진다. (1<=N<10,1<=K<100,000,000)
둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다.(1<=Ai<=1,000,000, A1=1, i>=2 인 경우에는 Ai-1의 배수)
[출력]
첫째 줄에 k원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.
[예제입력1]
10 4200
1
5
10
50
100
500
1000
5000
10000
50000
[예제 출력1]
6
[접근 방식]
Greedy 방식으로 K값과 가장 가까운 동전부터 개수를 계산한다.
1.큰 동전 부터 시작하여 K 값보다 작은 값인 경우, 최대 들어갈 수 이있는 동전의 개수를 구한다.
2. k값을 갱신한다.
3. coin의 개수를 추가한다.
1~3의 과정을 동전의 개수만큼 반복한다.
[코드]
#include<iostream>
#include<vector>
using namespace std;
int main() {
int K, N;
cin >> N >> K;
vector<pair<int, int>> coins; //coin 값, coin 개수
int answer=0;
for (int i = 0; i < N; i++) {
int temp;
cin >> temp;
coins.push_back(make_pair(temp, 0));
}
while (K!=0)
{
for (int i = N - 1; i >= 0; i--) {
if (K >= coins[i].first) {
int div = K / coins[i].first;
K = K - div * coins[i].first;
coins[i].second = div;
}
}
}
for (int i = 0; i < N; i++) {
answer += coins[i].second;
}
cout << answer;
return 0;
}