백준 - 2294 : 동전 2 (G5)

🏷️ python 🏷️ boj

수정일 : 2024-11-15


 1N, K = map(int, input().split())
 2V = []
 3for _ in range(N):
 4    V.append(int(input()))
 5dp = [[0]+([10001]*K) for _ in range(N+1)]
 6
 7for i in range(1, N+1):
 8    for j in range(1, K+1):
 9        if j >= V[i-1]:
10            dp[i][j] = min(dp[i-1][j], dp[i][j-V[i-1]]+1)
11        else:
12            dp[i][j] = dp[i-1][j]
13
14res = dp[N][K]
15
16print (res if res != 10001 else -1)
  • dp를 많이 풀어보자