[백준] 11047 동전0 c++

 

문제 링크 https://www.acmicpc.net/problem/11047

KEY

• 금액이 큰 단위부터 K값을 비교해 나가야 동전 개수가 최소가 된다.
• 따라서 금액 단위를 내림차순 정렬만 하면 되므로, 쉽게 접근할 수 있던 문제였다.

Code

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
#include<string>
using namespace std;
int N,K;
vector<int> v;
int answer;
 
int main() {
    cin >> N >> K;
    for (int i = 0; i < N; i++) {
        int coin;
        cin >> coin;
        v.push_back(coin);
    }
    sort(v.begin(), v.end(), greater<>());
 
    for (int i = 0; i < v.size(); i++) {
        if (K >= v[i]) { 
            answer += (K / v[i]); //몫만큼 더해주고
            K -= (K / v[i]) * v[i]; //몫에 coin을 곱한 금액을 빼준다.
        }
    }
    cout << answer;
}