[백준 11047] 동전 0

https://acmicpc.net/problem/11047

---

해설

이 문제는 https://far-simple.tistory.com/20 거스름 돈 문제와 매우 유사했다.

입력 되는 각각의 동전들을 내림차순으로 정렬해서 경우들을 따져주면 된다.

 

1) 큰 돈의 수부터 차례대로 가지고 있는 동전과 나누어보고 그 나눈 값을 카운트 해준다.

2) 가지고 있는 돈에서 각각의 동전에서 쓸 수있는 돈을 빼준다.

3) 돈이 0이 되면 카운트를 출력해주고 for문에서 탈출한다.

 

아마 위 설명만 보고는 이해가 안될 가능성이 높다.

이해하기 쉽게 코드를 길게 써놨으니 이해가 잘 안된다면 보는 것을 추천한다.

 

 

˙˙˙

 

소스코드

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int cnt;
int main(){
	vector<int> coin;
	int n, k; cin >> n >> k;
	
    for(int i=0; i<n; i++){
		int s; cin >> s;
		coin.push_back(s);
	}
	
    sort(coin.begin(), coin.end(), [](const int a, const int b){
		return a>b;
	}); //내림차순 정렬
	
    for(int i=0; i<coin.size(); i++){
		int p = k/coin[i];
		k -= coin[i]*p;
		cnt+=p;
		if(k==0){
			cout << cnt << '\n';
			break;
		}
	}
}