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

 

 

목차

 

 

---

 

 

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

 

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

11047번: 동전 0

 

---

 

해결전략

 

탐욕 알고리즘 (Greedy Algorithm)

 

탐욕 알고리즘 해결전략

1. 문제에 따라 최적해의 구성 요소를 선택하기 위한 기준을 정한다.
2. 초기 해답을 비어있는 상태 또는 어떠한 형태로 설정한다.
3. 선택 기준에 따라 해답에 요소를 추가하거나 선택한다.
4. 선택한 요소를 기준으로 다음 요소를 선택한다.
5. 만약 해답이 완성되지 않았다면 3단계부터 반복한다.
6. 모든 요소를 선택하고 해답이 완성되었을 때, 최종 해답을 반환한다.

 

---

 

코드

 

#include<iostream>
using namespace std;

int n, k, input, cnt;
int coin[11];

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> input;
		coin[i] = input;
	}

	for (int i = n; i > 0; i--)
	{
		while (k >= coin[i])
		{
			k -= coin[i];
			cnt++;
		}

		if (k <= 0) break;
	}

	cout << cnt;

	return 0;
}

 

---

 

더 나은 풀이

 

#include<iostream>
using namespace std;

int n, k, cnt=0;
int coin[11];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k;

	for (int i = 1; i <= n; i++) {
		cin >> coin[i];
	}

	for (int i = n; i > 0; i--)
	{
		if (k == 0) break;

		cnt += k / coin[i];

		k %= coin[i];
	}

	cout << cnt;

	return 0;
}

 

 

 

 

---