[백준 11047] 동전 0

0. 제목

• 백준 11047 동전 0
• BOJ 11047 동전 0
• C++ 11047 동전 0

---

1. 문제

https://www.acmicpc.net/problem/11047

---

2. 풀이

• 그리디 알고리즘을 사용하였다.
• 그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘 설계 기법이다.
• 동전의 가치가 오름차순으로 주어지기 때문에 가치가 큰 동전부터 차례대로 나눈다.
• 몫만큼 cnt에 더해주고 K를 나머지로 갱신해준다.
• 그렇게 모든 동전에 대해서 K/value[i]의 값이 0이 아닌동안 반복하면 누적된 cnt가 정답이다.

---

3. 코드

#include <iostream>
#include <vector>
using namespace std;
 
int main(void) {
    int N, K;    //N: 동전의 종류, K: 가치의 합
    cin >> N >> K;
    int money;    //vector원소
    vector<int> value;
    for (int i = 0; i < N; i++) {    //오름차순 입력
        cin >> money;
        value.push_back(money);
    }
 
    int cnt = 0;    //동전의 개수
    for (int i = N - 1; i >= 0; i--) {
        while (K / value[i]) {
            cnt += (K / value[i]);
            K %= value[i];
        }
    }
    cout << cnt;
    return 0;
}