[Python] 백준 2559 수열 - 그리디 알고리즘

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

 

예제입력:

10 4200
1
5
10
50
100
500
1000
5000
10000
50000

 

예제출력:

6

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
coins = [int(input()) for _ in range(N)]
coins.reverse()

re = 0
for coin in coins :
    re += K // coin
    K = K % coin

print(re)

- 오름차순으로 주어지는 동전을 리스트에 담고 reverse함수를 이용해 역순으로 정렬시킨다

- 정렬된 리스트내부를 순회하며 입력받은 돈을 순회한 값으로 나눈 몫을 result 변수에 더한다

   -> 나눠지지 않으면 0이 더해진다

- 그러고 K는 순회한 값의 나머지로 대입시킨다

   -> 입력받은 돈의 값보다 작아지면 그제서야 나눠지고, 나눠진 값을 K에 재대입