코테/Greedy
[C/C++] 백준 11047, Greedy
상똥
2022. 12. 10. 15:16
문제
코드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;
}