출처 : https://www.acmicpc.net/problem/11047
동전 0 성공
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 256 MB | 8555 | 4924 | 4090 | 58.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
출처
- 문제를 만든 사람: baekjoon
풀이
문제 조건의 (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;
}