백준 11047번: 동전 0

백준 11047번: 동전 0

아이디어

가장 비싼 동전부터 사용하면 동전을 최소한으로 사용할 수 있다. 사실 이게 가능한 이유는 각 동전의 금액이 서로 배수 관계이기 때문이다.
예를 들어, 1원, 7원, 18원짜리 동전으로 21원을 만드는 경우, 가장 비싼 동전인 18원짜리 동전을 먼저 사용하면 이후에 1원짜리 3개가 필요해서 총 4개의 동전을 사용하지만, 7원짜리 동전만 사용하면 동전 3개로 21원을 만들 수 있다.

코드

N, K = map(int, input().split())
value = [int(input()) for _ in range(N)]
cnt = 0
value.reverse()
for i in value:
    if i > K:
        continue
    else:
        cnt += K // i
        K %= i
print(cnt)

여담

왜 실버 2 문제인지 모르겠다.