[Baekjoon] 11047 동전0

알고리즘 분류

그리디 알고리즘

문제 - https://www.acmicpc.net/problem/11047

-문제-

가지고 있는 동전의 가치를 가지고 K원을 만드는 동전개수의 최소값을 출력하는 문제.

-해결방법- 

동전의 가치가 오름차순으로 정렬되어 있기 때문에 동전의 가치가 큰 값부터 K원을 나눠줌으로서 해결

<소스코드>

#include <cstdio> #include <iostream> int main() { int coin[10]; int money,i; int coin_num; int answer=0; scanf("%d %d", &coin_num,&money); for (i = 0; i < coin_num; i++) scanf("%d", &coin[i]); for (i = coin_num-1; i >= 0; i--) { if (coin[i]<= money) { answer += money / coin[i]; money = money % coin[i]; } } printf("%d\n", answer); return 0; }