[백준/Python] 11047 동전 0

문제

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

---

풀이

입력으로 들어온 동전들을 사용하여 K원을 만드는데 필요한 동전 개수의 최솟값을 출력하는 것이 목적이다 최적의 해를 구하기 위해선 가장 큰 화폐단위부터 거슬러주면 된다. n원을 거슬러줘야할 때 가장 큰 금액으로 거슬러 줄 수 있을만큼 거슬러 주고, 그 다음으로 큰 숫자만큼 거슬러주면 된다

---

코드

def solve(k):
    cnt = 0
    for i in coin:
        if k >= i:
            cnt += k//i
            k %= i
            if k <= 0:
                break
    return cnt
        

n, k = map(int,input().split())
coin = []
for _ in range(n):
    coin.append(int(input()))
coin.reverse()
print(solve(k))