[Baekjoon] 11047번: 동전 0

 

 

 

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

11047번: 동전 0

 

---

 

문제 해결 과정

착안

동전의 수를 최소화하기 위해 가능한 한 가장 높은 단위의 화폐부터 사용하여 주어지는 금액을 맞추고자 하였다.

 

구현

보유하고 있는 동전의 가치가 오름차순으로 주어지므로, 스택(stack) 자료 구조를 사용해 입력받는 순서로 동전의 가치가 맞추고자 하는 금액보다 작은 경우 이를 스택에 넣도록 구현하였다. 입력이 완료되면 스택으로부터 동전의 가치를 하나씩 차례대로 꺼내면서 나머지 연산자와 나눗셈 연산자를 사용해 맞추고자 하는 금액을 달성하도록 반복문을 구현하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <stack>

using namespace std;

stack<int> Coins;

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

	int N, Money, NumCoins = 0;
	cin >> N >> Money;

	while (N--)
	{
		int Coin;
		cin >> Coin;

		if (Coin > Money)
			break;

		Coins.push(Coin);
	}

	while (Money != 0)
	{
		int Coin = Coins.top();
		Coins.pop();

		NumCoins += Money / Coin;
		Money %= Coin;
	}

	cout << NumCoins << "\n";
	return 0;
}

 

실행 결과