[백준-실버3] 11047번 동전 0 (그리디, 파이썬)

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

11047번: 동전 0

 

<내 코드>

- 입력 받은 동전 coins를 내림차순으로 정렬했다. (큰 동전부터 파악해야 최소 갯수로 k원 만들 수 있기 때문에)

- 반복문을을 돌면서 만약 k // coins[i] > 0 이라면 즉, 몫이 있다면 cnt에 몫을 저장해주고, k는 나머지로 업데이트한다.

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
coins = []
for _ in range(n):
    coins.append(int(input()))
    
coins.sort(reverse = True) #내림 차순 정렬
cnt = 0
for i in range(n):
    if k // coins[i] > 0:
        cnt += k// coins[i]
        k = k % coins[i]
print(cnt)