[algorithm] 백준 11047 - 동전 0 (c++)

📚 문제

입력

출력

예제 입력 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

🧑🏻‍💻 풀이 과정

• 입력받은 동전을 큰 액수부터 낮은 액수로 내림차순 정렬하자.
• 반복하면서 큰 액수부터 k를 나눈 값을 cnt에 저장하자.
• 나머지 연산을 통해 k에서 액수만큼 빼주자.

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;

int n, k;
vector<int> v;
int cnt = 0;

int main() {
    cin >> n >> k;

    for (int i = 0; i < n; ++i) {
        int money;
        cin >> money;
        v.push_back(money);
    }

    std::reverse(v.begin(), v.end());
    for (int i = 0; i < v.size(); ++i) {
        cnt += k / v[i];
        k %= v[i];
    }

    cout << cnt << endl;
}