💡 그리디 알고리즘
Memory 1112KB Time 0ms Code Length 343B
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{
int n, k;
int coin_val[10]; // 동전 단위
scanf("%d %d", &n, &k);
for (int i = 0; i < n; i++) {
scanf("%d", &coin_val[i]);
getchar();
}
int cnt = 0;
for (int i = n - 1; i >= 0; i--) {
cnt += k / coin_val[i];
k %= coin_val[i];
}
printf("%d", cnt);
}
이 코드는 주어진 금액 k를 동전 단위로 나누어 최소한의 동전 개수를 구하는 프로그램이다. 먼저 n과 k를 입력받고, n개의 동전 단위를 입력받는다. 그 후, 큰 동전부터 시작하여 k를 해당 동전 단위로 나누고 남은 나머지를 다음 작은 동전 단위로 나누는 과정을 반복한다. 이를 통해 필요한 동전의 최소 개수를 계산하고 출력한다.
