백준 11047 동전 0 c++

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

11047번: 동전 0

그리디 문제다.

뺄 수 있는 최대한 큰 동전을  찾아서 그 동전을 사용 못할 때 까지 집는다.

만약 제일 작은 동전까지 반복했을 때 0이 되지 않았다면 전에 넣은 동전 하나 뺀다.

다시 반복

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <deque>
#include <unordered_set>
#include <cstring>
#include <utility>
#include <climits> // int32max

using namespace	std;

	int coinNum, target, res = 0, prevCoinIdx;
	vector<int> coin;

int	main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> coinNum >> target;
	for (int i = 0; i < coinNum; i++) {
		int input;
		cin >> input;
		coin.push_back(input);
	}
	for (int i = coin.size() - 1; i >= 0; i--) {
		if (target == 0)
			break ;
		if (target < coin[i])
			continue ;
		for (int j = 1; target >= coin[i]; j++) {
			prevCoinIdx = i;
			target -= coin[i];
			res++;
		}
		if (i == 0 && target != 0) {
			target += coin[prevCoinIdx];
			i = prevCoinIdx - 1;
		}
	}
	cout << res;
}