[백준] 11047번 C/C++ 풀이 _ 동전 0

 


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

시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초256 MB85554924409058.866%

문제

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

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

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

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

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최소값을 출력한다.

예제 입력 1 

10 4200
1
5
10
50
100
500
1000
5000
10000
50000

예제 출력 1 

6

예제 입력 2 

10 4790
1
5
10
50
100
500
1000
5000
10000
50000

예제 출력 2 

12

출처

풀이

문제 조건의 (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 를 유심하게 살펴보자.
이런 조건이 있으면, 큰 동전을 많이 사용하면 사용할 수록 최적의 답이 나올 수 있다. 

그리디 알고리즘을 이용하여 풀 수 있는 문제이다. 
동전을 큰 순서대로 다시 정렬한 다음에 현재 남은 돈에 몫이 존재하면 해당 몫을 코인에 추가해주고 K를 지속해서 갱신해주면 된다.
자세한 풀이는 소스코드를 통해서 전개하였다.

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <string.h>
using namespace std;

// main
int main(){
int N, K;
int coin = 0;
scanf("%d %d", &N, &K);
vector<int> coin_vec(N, 0);
for ( int n_idx = 0 ; n_idx < N; n_idx++)
scanf("%d", &(coin_vec.at(n_idx)));

sort(coin_vec.begin(), coin_vec.end(), greater<int>());

auto coin_iter = coin_vec.begin();
while(K){
int now_coin_num = K/(*coin_iter);
if(now_coin_num) coin += now_coin_num;
K = K - now_coin_num*(*coin_iter);
coin_iter++;
}

cout << coin;

return 0;
}