[백준-2294] 동전 2

풀이

dp[i]는 현재까지 입력받은 가치들의 합으로 i를 만드는 경우의 수이다.
입력이 1이들어오면 1의 합으로 i를 만드는 경우의 수를 구하고 그 다음 입력으로 2가 들어오면 1과 2의 합으로 i를 만드는 경우의 수를 구한다.
그리고 순서는 구성의 상관이 없으므로 현재 입력받은 수를 c라고 하면 dp[i]=min(dp[i],dp[i-c]+1)이다.

코드

import sys
input = sys.stdin.readline

n,k=map(int,input().split())
dp=[1000000]*(k+1)
dp[0]=0
li=[]
for _ in range(n):
    c=int(input())
    if c in li:
        continue
    li.append(c)
    for i in range(c,k+1):
        dp[i]=min(dp[i],dp[i-c]+1)

if dp[k]==1000000:
    print(-1)
else:
    print(dp[k])