백준 2294번: 동전2

import sys

input=sys.stdin.readline

n,k=map(int,input().split())

coins=[int(input()) for i in range(n)]


lst=[1e8 for i in range(k+1)]

lst[0] =0
for i in coins:
    for j in range(i,k+1):
        lst[j]=min(lst[j-i]+1,lst[j])

if lst[k]==1e8:
    print(-1)
else:
    print(lst[k])

 

 

디피 문제라는걸 알고 어떤식으로 해야 점화식을 잘 세워야할지 고민했다.

큰 문제를 작은 문제들로 나누어서 해결하고 마지막에 이제 문제를 해결해야된다고 생각을 했다.

처음에 내 생각에는 지금 k라는 수에 coins의 수들 중 가장 근접한 큰수를 나누고 이제 거기서 나머지 값이 k로 되어 또 거기서 근접한 큰 수를 나눠주면서 count를 해줘야된다고 생각했다.

그런데 이렇게 하면 조건문이 너무 많아지고 반복문도 어떻게 짜야될지 몰라서 구글링을 해보았다. 참고로 위의 내 방식은 그리디 알고리즘에 더 가깝다.

 

이제 dp알고리즘을 풀이해보겠다.

이전에 해결한 하위 문제의 결과를 저장하여 더 큰 문제를 해결할 때 사용하는 dp를 이용하면 한 코인의 값으로 k가 되려면 몇번 더해져야되는지 값을 이용해서 lst값을 업데이트 해줘야한다.

 

lst[j]는 금액 j를 만들기 위한 최소 동전 개수를 저장하는 배열

각 동전 종류를 사용해 금액을 만들 수 있는 최소 동전 개수를 점진적으로 업데이트

 

 

• 첫 번째 반복문 (for i in coins): 각 동전의 값을 순회
• 두 번째 반복문 (for j in range(i, k+1)): 해당 동전 i를 사용하여 금액 j를 만들기 위한 최소 동전 개수를 계산.
  • 우리가 lst[j-i]라는 값을 알고 있을 때, 이 값은 j-i라는 금액을 만들기 위해 필요한 최소 동전 개수를 의미한다. 이제 동전 i 하나를 추가로 사용하면, j-i라는 금액에서 j라는 금액을 만들 수 있게 되는 것이다.이렇게 계산한 값(즉, lst[j-i] + 1)과 이미 lst[j]에 저장된 값(5원을 만들기 위한 이전의 최소 동전 개수)을 비교해서, 더 작은 값을 선택하여 최소 동전 개수로 업데이트해준다.
  • 이렇게 하면 더 적은 동전으로 원하는 금액을 만들 수 있는 방법을 찾아가는 과정이 되는것이다.
  • 예를 들어, 5원을 만들고 싶을 때, 이미 2원을 만들 수 있는 방법을 알고 있다면, 여기서 동전 3원을 하나 추가해서 5원을 만들 수 있는것이다. 그러니까, 2원을 만드는 데 필요한 동전 개수에다가 동전 3원 하나를 더하는 것이다. 이때, 동전 하나를 더 사용하게 되니 +1을 더해주게 된다.

 

 

<i=1>

lst[0]	lst[1]	lst[2]	lst[3]	lst[4]	lst[5]	lst[6]	lst[7]	lst[8]	lst[9]	lst[10]	lst[11]	lst[12]	lst[13]	lst[14]	lst[15]
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15

 

<i= 5>

lst[0]	lst[1]	lst[2]	lst[3]	lst[4]	lst[5]	lst[6]	lst[7]	lst[8]	lst[9]	lst[10]	lst[11]	lst[12]	lst[13]	lst[14]	lst[15]
0	1	2	3	4	1	2	3	4	5	2	3	4	5	6	3

 

<i=15>

lst[0]	lst[1]	lst[2]	lst[3]	lst[4]	lst[5]	lst[6]	lst[7]	lst[8]	lst[9]	lst[10]	lst[11]	lst[12]	lst[13]	lst[14]	lst[15]
0	1	2	3	4	1	2	3	4	5	2	3	4	5	6	1