[dp/백준] 2294번: 동전2

-문제: https://www.acmicpc.net/problem/2294

동전단위 열부터 시작하기, dp구성하는 값 least upper bound로 설정하기

-정답풀이: 

n,k=map(int,input().split())
coins=[]
for _ in range(n):
    coins.append(int(input()))
dp=[10001]*(k+1)
dp[0]=0

for i in coins:
    for j in range(i,k+1):
        dp[j]=min(dp[j],dp[j-i]+1)
        
if dp[k]==10001:
    print(-1)
else:
    print(dp[k])

-시도한 풀이:

이게 왜 안되는지 잘 모르겠다. python tutor를 돌린 결과 예시는 일단 잘 돌아가는데,,

j의 범위가 달라서 틀린 것 같기도하고,,,

왜 틀렸는지 잘 모르겠네

n,k=map(int,input().split())
coins=[]
for _ in range(n):
    coins.append(int(input()))
dp=[0]*(k+1)

for i in coins:
    for j in range(1,k+1):
        if j%i ==0:
            dp[j]= j//i
        elif j>i:
            dp[j]=min(dp[j],dp[j%i]+(j//i))
if dp[k]==0:
    print(-1)
else:
    print(dp[k])