(C++) 백준 11047번 - 동전 0

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

문제

> 준규가 가진 동전은 총 N종류고 각각 매우 많이 가지고있다.
> 동전을 적절히 사용해 가치의 합을 K로 만들려고 할때 개수의 최소값을 구해라.

접근

그리디 알고리즘을 사용하면 쉽게 할 수 있다.

문제해결

> 가치를 입력받아 coin 벡터에 저장한다.
> 그리디를 사용해 큰 가치의 동전을 가장 많이 쓸 때부터 탐색한다. 그래서 역순으로  coin벡터를 비교한다.
> 불필요한 연산을 줄이기 위해 가치가 K보다 클때를 전부 패싱한다. K/coin[i]로 사용한 동전을 누적하고 K의 값을 나머지로 갱신해 다음 연산을 이어가고 cnt를 출력한다.

코드

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

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

	int N, K;
	cin >> N >> K;

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

	int cnt = 0;
	for (int i = coin.size() - 1; i >= 0; i--)
	{
		if (coin[i] > K) continue;
		cnt += K / coin[i];
		K %= coin[i];
	}
	cout << cnt << '\n';
}

후기

브론즈에서 그리디를 사용해 설탕 배달 문제를 풀어봤어서 어렵지 않게 풀었다.