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

 

문제 11047번

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

 

n의 최댓값이 10이기 때문에 크기가 11인 배열 하나를 만들어준다. 입력값들을 배열에 차례대로 넣어주고, 동전 개수를 최소로 하기 위해 가장 큰 가치를 가진 맨 뒤부터 반복문을 돌려준다.

 

그리고 k에서 동전들을 빼가며 0보다 크거나 같다면 계속해서 반복해준다. 그 안에서는 개수를 count해주고 k의 값을 줄여나간다. 그렇게 반복문을 마치고 sum을 출력하면 그것이 k원을 만드는데 필요한 동전 개수의 최솟값이다.

#include <iostream>
using namespace std;

int main() {
	int n, k, sum = 0;
	int num[11];
	cin >> n >> k;

	for (int i = 0; i < n; i++) {
		cin >> num[i];
	}
	for (int i = n - 1; i >= 0; i--) {
		while (k - num[i] >= 0) {
			sum++;
			k -= num[i];
		}
	}
	cout << sum;

	return 0;
}