[BOJ/백준 11047][C++] 동전 0

문제

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

 

문제 내용

동전을 적절히 사용해서 K원을 만드는 문제이다.
이때 동전의 최소화하여 사용하는 것이 이 문제의 핵심이다.

 

문제 풀이

이 문제는 greedy한 성격이 있다.

4200원을 만들 때, (1원짜리 4200개) / (100원짜리  420개) / (1000원짜리 4개 + 100원짜리 2개) 등 여러 방법으로 만들 수 있다.
이 경우 (1000원짜리 4개 + 100원짜리 2개)로 4200원을 만드는 것이 동전의 개수를 최소화할 수 있다.

 

그럼 이 문제를 풀 때 어떻게 해야 할까?

동전의 가치가 큰 것부터 사용하는 방식을 선택하면 된다. 
만들려는 K원보다 가치가 작은 동전들 중에서, 그나마 가치가 큰 동전부터 사용하면 된다.

 

코드

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

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	//입력
	int n, k,tmp;
	cin >> n >> k; //동전 종류, 만들려는 합

	vector<int>v;
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		v.push_back(tmp); //동전의 가치가 오름차순으로 주어짐
	}

	//문제 해결
	int count = 0;
	for (int i = v.size() - 1; i >= 0; i--) { //가치가 큰 동전부터
		if (k == 0) break;

		if (k >= v[i]) { //K원보다 작거나 같은 동전을 사용
			count += (k / v[i]); //v[i] 동전을 몇개나 사용할 수 있는지
			k = k % v[i]; //나머지는 남겨둔다
		}
	}

	//결과 출력
	cout << count << '\n';
}

 

문제 코드 설명

1) 문제 해결

count 변수는 우리가 구하고자 하는 'K원을 만드는데 필요한 동전의 개수의 최소값'이다.

입력받은 동전들의 벡터 v는 오름차순으로 저장이 되어있다.
그렇기 때문에 for문을 돌 때 역순으로 돌아서 가치가 큰 동전부터 사용할 수 있도록 했다.

K가 0이 되었다는 뜻은 주어진 동전들로 K를 만들었다는 의미로 반복문을 빠져나갈 수 있도록 break를 쓴다.

K>=v[i] 라는 조건이 있는 이유는 동전들로 K원을 만들기 위해서는 K원보다 가치가 작은 동전을 사용해야 하기 때문이다.
위 조건을 만족시켰다면,  K원을 만들기 위해 v[i] 동전을 몇 개나 사용해야 할지를 구하고, 이를 count변수에 더해준다.
이후, K에는 v[i]동전을 사용하고 남은 나머지를 다시 저장해주면 된다.