알고리즘/BaekJoon

[c++] 11047번 : 동전 0

__jhp_+ 2022. 9. 2. 16:09

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

 

11047번: 동전 0

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

www.acmicpc.net

#include <iostream>

using namespace std;

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

	int arrCoin[10] = { 1, };
	int N, K, cnt = 0;
	cin >> N >> K;
	for (int i = 0; i < N; ++i)
	{
		cin >> arrCoin[i];
	}

	int index = N - 1;
	while (K > 0)
	{
		int tmp = K / arrCoin[index];
		if (tmp > 0)
		{
			cnt += tmp;
			K %= arrCoin[index];
		}
		--index;
	}
	cout << cnt << '\n';
	return 0;
}