[백준]2294 동전2 #dp

1. 풀이

dp[i][j] : i번째 동전까지 이용해서 j원을 만들때 가능 한 최소동전개수.

i번째 동전까지 이용해서 j원을 만들때 가능 한 최소 동전개수는 i-1번째 동전까지 이용했을때 j를 만드는 경우와

(j-(i번째동전의 금액))최소동전수+1 한 경우 중 최소 값을 선택하면 된다.

​

따라서 점화식은 아래와 같다

dp[i][j]=min(dp[i][j-i번째 동전의금액]+1,dp[i-1][j])

​

이때 dp를 2차원으로 만들었을 때 바로 위에 행과 비교를 하기 때문에 1차원 dp 리스트를 만들어도 상관이 없다.

=> 1차원 for문에서 i번째 반복을 마친 상태가 결국 2차원 dp의 i행

따라서 메모리를 최적화 시키기 위해 1차원으로 dp를 생성한다.

​

2. 소스코드

n,k=map(int,input().split())
money=[]
INF=9876543210
for i in range(n):
    money.append(int(input()))
dp=[INF for i in range(k+1)]
dp[0]=0
for i in range(n):
    for j in range(k+1):
        if j-money[i]>=0:
            dp[j]=min(dp[j],dp[j-money[i]]+1)


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