[BOJ 11047, Python 3] 동전 0

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

11047번: 동전 0

 

풀이

동전의 개수를 최소로 해서 합 K를 만들어야하므로 내림차순으로 정렬해서 몫을 이용해 몇 개의 동전을 사용할 수 있는지 확인하여 그만큼 값을 K에 빼주면 된다.

코드

n, k = map(int, input().split())
arr = sorted([int(input()) for i in range(n)], reverse=True)
ans = 0
for i in range(n):
    val = k // arr[i]
    ans += val
    k -= arr[i] * val
print(ans)