(Python) - BOJ(11047번) : 동전 0

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

11047번: 동전 0

---

• 해설 : 

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

 

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

 

 

 

---

• 풀이 :

동전의 가치가 높은 순서대로 선택할 수 있는 갯수를 모두 선택하여 동전 개수의 최솟값을 구하는 그리디한 문제이다. 

 

 

 

---

• 소스코드 : 

 

n, k = map(int, input().split())
m = []
num = 0
for i in range(n):
    m.append(int(input()))
for i in range(n - 1, -1, -1):
    if k == 0:
        break
    if m[i] > k:
        continue
    num += k // m[i]
    k %= m[i]
print(num)