[BAEKJOON] 11047 동전 0

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

나의 접근

1. (이 문제에 한하여) 동전의 단위가 규칙적이다.

2. 작은 단위의 동전으로 큰 단위의 동전을 만들 수 있다.

=> 너무나 전형적인 그리디 알고리즘

나의 풀이

N, K = map(int, input().split())
coins = []
count = 0
for i in range(N):
    coins.append(int(input()))
coins.sort()

for i in range(N-1, -1, -1):

    cnt = K // coins[i]

    K -= cnt * coins[i]
    count += cnt
print(count)

소요 시간

10분