[C++]백준11047번 동전 0

오늘은 백준11047번 동전 0 문제를 풀어보도록 하자.

그리디 문제로 코드 수도 얼마 나오지 않는 쉬운 문제 되시겠다. :)

문제는 다음과 같다.

                               [접근법]

  1. 동전의 가짓수를 최소로 한다 -> 처음부터 큰 값으로 접근한다. (입력 값이 오름차순이라 정렬할 필요 X)

  2. 벡터에 입력 값을 저장하여 v[i]가 K보다 작거나 같으면 cnt를 늘리고 K는 v[i]로 나눈 나머지 값으로 갱신해준다.
  
  3. A1 = 1이기 때문에 못 만들 조합이 없으므로 편하게 예외처리 없이 for문을 돌려주시면 되시겠다.

                                     [코드]
#include <iostream>
#include <vector>
using namespace std;

int main() {
	vector<int>v;
	int won, N, K, cnt = 0;

	cin >> N >> K;

	for (int i = 0; i < N; i++) {
		cin >> won;
		v.push_back(won);
	}
	for (int i = v.size() - 1; i >= 0; i--) {
		if (v[i] <= K) {
			cnt += K / v[i];
			K %= v[i];
		}
	}
	cout << cnt << '\n';
	return 0;
}