백준 11047번 동전 0 파이썬

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

11047번: 동전 0

 

답안

n, k = map(int, input().split())
coin = []
cnt = 0
for _ in range(n):
    coin.append(int(input()))
coin.sort(reverse = True)

for i in coin:
    if k >= i:
        cnt += (k // i)
        k %= i
        
print(cnt)

---

그리디 알고리즘의 기초인 거스름돈 문제를 해결해 보았다.

이 문제는 큰 화폐가 작은 화폐의 배수 이기 때문에 쉽게 해결 할 수 있었다.

 

 

그리디 알고리즘 참고

https://thingjin.tistory.com/entry/%EA%B7%B8%EB%A6%AC%EB%94%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Greedy-Algorithm-Python

그리디 알고리즘 ( Greedy Algorithm ) - Python