[python] 11047번 - 동전 0

문제

파이썬 문제 풀이

동전의 개수를 최소로 하기 위해서는 가장 비싼 동전으로 최대한 바꾸고, 나머지에 대해 그다음 비싼 동전으로 바꿔가면서 나머지가 0이 되도록 하는 방법을 사용한다.

import sys
input = sys.stdin.readline

N, K = list(map(int, input().rstrip().split()))

coin = []
for i in range(N) :
  coin.append(int(input().rstrip()))

coin.reverse()
count = 0

for i in coin:
  if K == 0 :
    break
  count += (K // i)
  K %= i

print(count)

가장 비싼 동전부터 접근하기 위해 오름차순으로 입력받은 동전을 reverse해줘 내림차순으로 바꾸어주었다.

count는 동전의 수이다. 현재 동전으로 줄 수 있는 만큼(몫)을 count에 더해주고 나머지를 다음 동전으로 바꾸어 주도록 K에 다시 저장하였다.