백준 11047번 : 동전 0

문제.

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

11047번: 동전 0

 

- 아이디어 :

각 화폐가 배수 관계이므로, 큰 단위의 화폐부터 사용할 개수를 구하면 필요한 동전 개수가 최소가 된다.

각 화폐의 개수는 주어진 금액 // 화폐 로 구할 수 있다.

 

 

- 구현 :

n, k = map(int, input().split()) 
kind = []
total = 0 # 필요한 동전의 총 개수
for i in range(n):
  value = int(input())
  kind.append(value)

kind.sort(reverse=True)
for coin in kind :
  cnt = k // coin # 화폐별 필요한 코인 개수
  k -= (coin * cnt)
  total += cnt

print(total)

 

대표적인 그리디 알고리즘 문제이다.