백준 11047번(그리디)

11047번(그리디)

이 문제도 거스름돈 거슬러주기와 매우 유사한 문제였습니다. 오히려 조금 더 쉬운 느낌이었습니다. 애초에 입력 자체가 오름차순으로 주어져서 더욱 쉽게 느낀 것 같습니다. 입력 받을 때 만들어야할 값보다 작은 동전 값을 확인후 그 동전 값으로 주어진 값을 나누고 그 결과를 저장한 했습니다. 그리고 나눈 뒤의 나머지 값으로 이 과정을 반복하는 것으로 이 문제를 해결하였습니다.

#include <iostream>
#include <vector>

using namespace std;

int main() {
	int n = 0;
	int k = 0;
	int result = 0;
	int num = 0;
	int idx = 0;
	vector<int> coin;

	cin >> n;
	cin >> k;

	for (int i = 0; i < n; i++) {
		cin >> num;
		coin.push_back(num);
		if (num <= k) {
			idx = i;
		}
	}
	
	int remainder = k; // 초기 나머지 값을 k로 설정

	while (remainder != 0) {
		if (coin[idx] > remainder) { // 나머지가 현재 idx인덱스의 코인보다 작으면 바로 다음으로
			idx--;
			continue;
		}
		result += remainder / coin[idx];
		remainder = remainder % coin[idx];
		idx--;
	}

	cout << result;

	return 0;

}