[알고리즘/백준] 2294번 : 동전 2(python)

이전의 코인에 +1을 하는 경우와, 자기자신이 가장 작은 경우로 나눠서 작은걸 선택하면 된다.

n, k = map(int, input().split())
a = list(int(input()) for _ in range(n))

if k in a:
    print(1)
    exit()

dp = [10001] * (k + 1)
dp[0] = 0
for i in a:
    for j in range(i, k + 1):
        dp[j] = dp[j] if dp[j] < dp[j - i] + 1 else dp[j - i] + 1
if dp[k] > 10000:
    print(-1)
    exit()
print(dp[k])