동전 0 [ Python ] [ 백준 : 11047 ]

---

풀이 및 회고

 

제가 좋아하는 그리디 문제입니다. 이 문제를 푸는데는 이코테 책이 도움이 되었습니다. 책에서 나온 거스름돈 문제와 상당히 유사했습니다.

문제를 보자마자 그 로직을 떠올릴 수 있었고 실행에 옮겼습니다. 이게왠일 한번에 통과되어 기쁨을 만끽했습니다 허허허허

# 동전 0

n, k = map(int, input().split())

coin = []

for i in range(n):
    coin.append(int(input()))

coin.sort(reverse=True)

count = 0
for i in coin:
    count = count + k // i 
    # k = 4200 , i = 5000 일땐 몫이 없기떄문에 0 이들어감
    # k = 4200 , i = 1000 일때 나눈 몫 4 를 count 에 더해준다.
    k = k % i
    # k = 4200 , i = 5000 일때 나머지 가 성립이 안되므로 k 의 값은 변화없음
    # k = 4200 , i = 1000 일때 나머지는 200 이므로 200 이 들어감

print(count)