동전 0 (백준 - 11047번)

동전의 가치가 가장 높은 것 부터 순차적으로 내려가면서 K보다 가치가 작았을때 그 가치만큼의 동전의 개수를 구해 (나눠주고) 최종값에 더해주고 나머지 값이 있으면 아직 동전을 충분히 채우지 못했으므로 반복해주면 된다. 

 

4200원

동전의 가치

1, 5, 10, 50, 100, 500, 1000, 5000, 10000, 50000

[1]

50000 -> 10000 -> ... -> 1000(알맞는값)

4200 / 1000 = 4개 

4200 - (1000  * 4) = 200원

 

[2]

1000 -> 500 -> 100(알맞는값)

200 / 100 = 2개

200 - (200 * 2) = 0원(분기 종료)

 

[최종]

4개 + 2개 = 6개

#include <iostream>
using namespace std;

int main()
{
	int input_count = 0; 
	int price = 0;
	cin >> input_count >> price;

	int* coins = new int[input_count];
	for (int i = 0; i < input_count; ++i)
		cin >> coins[i];

	int index = input_count - 1;
	int coin_count = 0;

	while (0 < price)
	{
		if (price < coins[index])
		{
			--index;
			continue;
		}

		int times = price / coins[index];
		int rest = price % coins[index];

		coin_count += times;
		price = rest;	

		--index;
	}

	cout << coin_count << endl;	
	delete[] coins;
}