728x90
https://www.acmicpc.net/problem/11047
문제
준규가 가지고 있는 동전은 총 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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.
코드
#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <vector>
using namespace std;
int N, K;
vector<int> A;
int ans = 0;
int main(void){
cin >> N >> K;
for(int i=0; i<N; ++i){
int a;
cin >> a;
A.push_back(a);
}
int maxx = A[N-1];
while(K != 0){
for(int i=0; i<N; ++i){
if(K/A[i] ==0){
maxx = A[i-1];
break;
}
}
ans += K/maxx;
K -= (K/maxx) * maxx;
}
cout << ans;
return 0;
}
그리디 알고리즘의 가장 대표적인 문제이다.
그리디 알고리즘을 간단하게 설명해 보자면 말그대로 탐욕적인 알고리즘으로 '현재'의 기준에서 어떻게 하면 가장 최적화된 답을 도출할 수 있을까에 대한 답을 내놓는 알고리즘이다.
예를 들어 현재 문제인 동전0는 동전 개수의 최소값을 구하는 문제인데 이 최소값을 구하려면은 가장 큰 종류의 동전을 먼저 소비하고 뒤에는 내림차순대로 동전을 소모해 K원을 만들면 동전 개수가 가장 최소값이 나오게 된다.
말 그대로 먼저 소비할 수 있는 가장 큰 동전을 소비해나가면 최소값을 찾을 수 있는데 이와 같이 앞의 선택이 이후의 선택에 영향을 주지 않는다면 그리디 알고리즘을 활용할 수 있다.
728x90
반응형
'PS > Greedy' 카테고리의 다른 글
[1744] 수 묶기 (0) | 2023.07.18 |
---|---|
[2138] 전구와 스위치 (0) | 2023.07.18 |
[1931] 회의실 배정 (0) | 2023.05.02 |