[백준][Python] 2294번 동전 2

2294번: 동전 2

 

 

코드

import sys

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

for c in cost:
	for i in range(1,k+1):
		if i-c >= 0:
			dp[i] = min(dp[i-c]+1,dp[i])

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

 

설명

k의 최댓값이 10000이기 때문에 사용하는 동전의 개수가 10000을 넘지 않는다. 따라서 dp의 초기값을 모두 10001로 두었다.

예시를 보면 처음에 c의 값이 1이기 때문에 dp의 값을 1만 사용했을 때 필요한 동전의 개수로 바꾸게 된다. 다음 값은 c가 5일 때이고, 5를 사용해서 동전을 더 적게 사용할 수 있으면 min(dp[i-c]+1,dp[i])를 통해 dp 값을 바꿔준다. 이 과정을 반복하게 되면 dp[k]의 값을 구할 수 있다.