[C/C++] 백준 11047, Greedy

문제

11047번: 동전 0 (acmicpc.net)

11047번: 동전 0

코드1

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
	int n, k;
	int t;
	int m = 0;
	vector<int> arr, cnt; //arr:동전의 액면가, cnt: 동전의 개수

	scanf("%d %d", &n, &k);
	for (int i = 0; i < n; i++) {
		scanf("%d", &t);
		arr.push_back(t);
	}

	sort(arr.begin(), arr.end());
	reverse(arr.begin(), arr.end());

	int c;
	for (int i = 0; i < n; i++)
		cnt.push_back(0);

	for (int i = 0; i < n; i++) {
		if(arr[i] > k)
			continue;
		c = k / arr[i];
		cnt[i] = c;
		k = k - c * arr[i];
		if (k == 0)
			break;
	}

	for (int i = 0; i < n; i++)
		m += cnt[i];
	printf("%d\n", m);
}

코드2

#include <stdio.h>
#include <iostream>

using namespace std;

int main() {
	int N, K, sum = 0;
	int coin[10];
	cin >> N >> K;
	for (int i = 0; i < N; i++)
		cin >> coin[i];

	for (int i = N - 1; i > -1; i--) {
		if (K == 0)
			break;
		if (K >= coin[i]) {
			sum += K / coin[i];
			K %= coin[i];
		}
	}

	cout << sum;
}