[Python] 백준 #11047 - 동전 0

문제

---

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

11047번: 동전 0

 

 

풀이

---

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

for i in sorted(arr,reverse=True):
    if k >= i :
        cnt+=k//i
        k=k%i
print(cnt)

 

그리디 알고리즘으로 풀면된다.

뒷 일은 생각하지 않고 현재 가장 좋은 방법으로 푸는 방식이다.

 

동전의 가치가 큰 것들로 이뤄져야지 동전 개수가 최소가 된다.

그렇기 때문에 동전의 가치를 내림차순으로 정렬해준다.

 

정렬된 동전의 가치를 순회하면서, 가지고 있는 돈이 동전의 가치보다 크다면 그 동전을 사용할 수 있다.

가지고 있는 돈을 동전의 가치로 나눈 몫이 동전의 개수가 되고 나머지가 남은 돈이된다.