[BOJ] 11047 동전 0 - 그리디 알고리즘

큰 동전의 액면가는 작은 동전의 액면가로 무조건 나누어 떨어진다.

다음과 같은 식이다.

5000 1000 500 100 50 25 5

 

따라서 문제는 간단해진다.

작은 액면가의 동전을 큰 액면가의 동전으로 바꾸어 나가면 된다.

간단한 예를 들어보자.

280원을 만드려고 한다면,

우선 5 원짜리 56개로 시작한다.

5원 짜리에서 25원 짜리로 가기위해선 5원짜리 5개가 필요하다.

 

25원짜리 11개와 5원 짜리 1개로 바꾼다.

위와 같은 식으로 그냥 바꿔나가기만 하면 답이 된다.

너무 간단하다.

 

#include <iostream>

int Balance[11] = { 0 , };
int CoinValues[11] = { 0 , };
int N = 0;
int K = 0;

int main()
{
	std::cin.tie(0);
	std::cout.tie(0);

	std::cin.sync_with_stdio(false);
	std::cout.sync_with_stdio(false);

	std::cin >> N;
	std::cin >> K;

	for (int i = 1; i <= N; ++i)
		std::cin >> CoinValues[i];

	Balance[1] = K;

	int Ans = 0;

	for (int i = 2; i <= N; ++i)
	{
		int Quotient = Balance[i - 1] / CoinValues[i];

		Balance[i] = Quotient * CoinValues[i];
		Balance[i - 1] = Balance[i - 1] - Balance[i];
	}

	for (int i = 1; i <= N; ++i)
		Ans += Balance[i] / CoinValues[i];

	std::cout << Ans;


	return 0;
}