[C++] 백준 11047: 동전 0

문제

[C++] 백준 11047: 동전 0 SILVER 4
https://www.acmicpc.net/problem/11047

 

---

 

접근 방법

이 문제는 주어진 동전들을 이용해 합이 K가 되도록 만들 때 필요한 최소 동전 개수를 구하는 문제이다.
각 동전은 무한히 사용할 수 있고, 동전의 가치들은 오름차순으로 주어진다.

이 문제의 핵심은 그리디 알고리즘이다.
항상 가치가 가장 큰 동전부터 최대한 사용하는 것이 최적이라는 조건이 보장되어 있다.

그래서 다음과 같은 방식으로 접근했다.

1. 동전 배열의 가장 뒤(가장 큰 가치) 부터 확인한다.
2. 현재 동전이 k보다 작거나 같다면,
   • k / coin[i] 만큼 사용할 수 있고
   • 사용한 만큼 k %= coin[i]로 남은 금액을 갱신한다.
3. 모든 동전을 확인할 때까지 반복한다.

이 과정을 거치면 최소 동전 개수를 구할 수 있다.

 

구현 시 주의할 점

• 반드시 큰 가치의 동전부터 사용해야 한다.
  작은 동전부터 사용하면 최적해를 보장할 수 없다.
• 문제에서 주어진 동전 체계는 그리디가 항상 성립하는 구조이므로
  동적 계획법(DP)을 사용할 필요가 없다.
• k와 동전의 값이 클 수 있으므로 연산 과정에서 long long 타입을 사용하는 것이 안전하다.

 

---

 

코드

#include <iostream>
#include <vector>
using namespace std;

typedef long long LL;

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

	LL n = 0, k = 0;
	cin >> n >> k;

	vector<LL> coin(n, 0);
	for (int i = 0; i < n; i++)
		cin >> coin[i];

	LL cnt = 0;
	for (int i = n - 1; i >= 0; i--)
	{
		if (coin[i] <= k)
		{
			cnt += (k / coin[i]);
			k %= coin[i];
		}
	}
	cout << cnt;

	return 0;
}