백준 11047번 동전0 C++ 풀이

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

11047번: 동전 0

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

 

현재 가지고 있는 돈을 최소의 지폐로 환산하면 몇 장인지 구하는 문제로, 그리디 알고리즘을 사용할 수 있는 문제이다.

 

문제의 포인트

문제를 보고 구현할 수 있는가?

최적의 방법을 찾을 수 있는가?

코드

#include<iostream>
using namespace std;
int a[10];
int main()
{
	int n, k;
	cin >> n >> k;

	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	int cnt = 0;
	for (int i = n-1; i >= 0; i--)
	{
		if (a[i]<=k) //현재 돈에 낼 수 있는 최대 화폐 찾으면
		{
			cnt += k / a[i]; //그 지폐로 얼마나 낼 수 있는지 체크
			k %= a[i]; //남은돈만 가진다
		}
	}
	cout << cnt;
}

여담

간단하게 풀 수 있는 문제였다. for문 범위체크할 때 >=0이 아닌 >0이라고 써서 한 번 틀린적은 있다. 조심해야지.