[백준] 11047번 - 동전 0

---

문제 분석

문제의 설명을 보면 뒤의 동전 가격 A[i]가 A[i-1]의 배수가 된다고 하였으므로, 원하는 동전 값 K를 최소의 동전을 이용해서 만들기 위해서는 가장 가격이 큰 동전부터 차례대로 사용하면 된다.
따라서 그리디 알고리즘을 떠올릴 수 있다.

---

소스 코드

# 동전 0

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
arr = []
count = 0

for _ in range(N):
    arr.append(int(input()))

for i in range(N-1, -1, -1):
    if arr[i] <= K:
        count += K//arr[i]
        K %= arr[i]
        if K == 0:
            break

print(count)