동전 0(그리디)

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

1. 코드

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

a = [int(input()) for i in range(n)] # 지폐 입력

c = 0

for i in reversed(range(n)):  # 역방향으로

  if k ==0:
    break
  
  if a[i] <= k:
     c += k // a[i]
     k %= a[i]

print(c)

2. 아이디어

배수이기 때문에 그리디를 사용할 수 있다.
이 조건이 없다면, 800원 가치중, 500 400 100이 주어지게되어 그리디가 안된다.