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

🌽 문제

🥕 입출력

🥔 풀이

동전의 액수는 그보다 한 단계 적은 액수의 동전의 배수이므로
고민 없이 바로 그리디를 적용할 수 있다.

입력받은 동전의 액수를 뒤에서부터(큰 액수부터) 돌면서
K보다 적거나 같은 액수가 나오면 cnt를 계산한다.

cnt에는 K를 동전의 액수로 나눈 값을 더해주고,
K는 나누어 남은 나머지값으로 갱신해준다.
목표 금액을 채웠다면 break하여 빠져나온다.

🥬 코드

#include <iostream>
#include <vector>
using namespace std;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, K;
	cin >> N >> K;
	vector<int> coin(N);
	for (int i = 0; i < N; i++) cin >> coin[i];

	int cnt = 0;
	for (int i = N - 1; i >= 0; i--) {
		if (coin[i] > K) continue;
		cnt += K / coin[i];
		K %= coin[i];
		if (K == 0) break;
	}
	cout << cnt;

	return 0;
}

🥜 채점