[파이썬] 백준 - 11047: 동전0

---

문제

11047번: 동전 0

---

풀이

그리디 알고리즘으로 푸는 문제.

동전 갯수를 최소로 만들기 위해서는 동전 액수를 내림차순으로 나눌 수 있는 가장 큰 수 부터 나누면 된다.

이 문제는 나누어 떨어지지 않는 조건은 없기 때문에 간단함.

n, k = map(int, input().split())
coins = []
for i in range(n):
    coins.append(int(input()))
result = 0

coins = coins[::-1]	# 내림차순으로 정렬
for i in range(n):
    if k // coins[i] > 0:	# 나눌 수 있다면
        result += k // coins[i]	# 나누어 발생한 몫 즉, 동전 갯수
        k = k % coins[i]	# 나머지를 다시 for문으로 계속 나눈다
print(result)