🔗 문제 링크

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

💻 코드

N, K = map(int, input().split())

A = [] * N

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

A.sort(reverse=True)

result = 0
for i in A:
    if i > K:
        continue
    else:
        result += K // i
        K = K % i

print(result)

설계

가치가 큰 동전이 가치가 작은 동전의 배수이므로, K보다 가치가 작고 그 중에 가치가 큰 동전부터 필요한 동전 개수에 포함시킨다.
이 그리디 알고리즘은 동전의 가치가 배수로 주어졌기 때문에 가능하다.