[Python | 파이썬] 백준 11047 동전0

[Python | 파이썬] 백준 11047 동전0 

 

 

이 문제는 그리디 알고리즘으로 해결할 수 있다. 이유는 각 동전의 값이 다른 동전의 값의 배수이기 때문이다.

따라서 동전을 내림차순으로 정렬한 뒤에 현재 금액을 가장 큰 동전의 금액으로 나눈 몫을 result에 추가해주고, 나눈 나머지를 현재 금액으로 갱신해주면 된다.

n, k = map(int, input().split())
coin = []
for i in range(n):
    coin.append(int(input()))

rst = 0
coin.sort(reverse=True)
for c in coin:
    rst += k // c
    k %= c
print(rst)

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