[BOJ] 11047 - 동전 0

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

11047번: 동전 0

n , k = map(int, input().split())
array = list()
num = 0
for i in range(n):
    array.append(int(input()))

for i in reversed(array):
    coin = i
    num += k // coin
    k %= coin

print(num)

이 문제는 그리디 알고리즘을 이용하여 풀 수 있는 가장 간단하고 대표적인 문제이다.

풀이 방법은 가장 큰 단위의 화폐부터 가장 작은 단위의 화폐까지 차례로 확인하여 나가는 것이다.

그리디 알고리즘의 특성 상 정당성을 검증해야 하는데, 입력 값을 보면 모든 동전의 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 조합해 다른 해가 나올 수 없다. 따라서 이는 항상 최적의 해를 주기 때문에 정당하다.