[백준 11047번] 동전 0 - python

문제 링크

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

11047번: 동전 0

풀이

- 그리디 문제

- 숫자가 큰 동전을 최대한 많이 사용해야 필요한 동전의 개수가 줄어든다. 

따라서 큰 동전부터 cnt 에는 동전의 가치를 동전으로 나눈 몫을 더하고, 

동전의 가치는 동전으로 나눈 나머지로 갱신해준다. 

동전의 가치가 0보다 클 때 위 과정을 반복한다. 

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

coin = []

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

# 동전의 가치가 큰 것부터 
coin.sort(reverse = True)

# 동전의 인덱스 
i = 0 
# 필요한 동전의 개수 
cnt = 0 
# 동전의 가치가 0보다 클 때 
while k > 0:
  cnt += k // coin[i] 
  k = k % coin[i]
  i += 1 

print(cnt)