이번 문제는 다이나믹 프로그래밍을 통해 해결하였다. dp리스트를 k+1의 크기로 선언하고, 1e9로 채운다. 그리고 동전과 dp를 순회하며 현재 가격에 해당하는 동전의 갯수와 현재가격-동전의가치에서의 동전의 갯수+1를 비교하여 더 작은 값을 취하도록 하였다. 점화식은 다음과 같다.

dp[i] = min(dp[i], dp[i-coin]+1)

Code

n, k = map(int, input().split())
coins = [int(input()) for _ in range(n)]
dp = [1e9 for _ in range(k+1)]
dp[0] = 0
mx = 0
for i in range(n):
    for j in range(coins[i], k+1):
        dp[j] = min(dp[j], dp[j-coins[i]]+1)
if dp[k] == 1e9:
    print(-1)
else:
    print(dp[k])