문제

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

풀이

그리디 알고리즘의 대표적인 예로 거스름 돈 문제이다.
큰 단위가 작은 단위의 배수이기 때문에 그리디 문제로 해결할 수 있다.
만약 배수가 아니라면 다른 방법을 생각 해야한다.

코드

import sys
input = sys.stdin.readline

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

a = []
for _ in range(N):
    a.append(int(input()))

a.reverse()
count = 0

for i in a:
    if K >= i:
        count += K // i
        K %= i
        if K == 0:
            break

print(count)