BOJ-2294 - Python

n개의 동전이 입력되며 합이 k원이 되도록 할 때 동전의 최소 개수를 출력하는 문제. 최댓값인 10001로 k+1 크기의 배열을 이용하여 다이내믹 프로그래밍 방법을 이용하여 풀었다. dp[j] = min(dp[j], dp[j-coin]+1)의 점화식을 이용하였으며 coin은 입력되는 동전의 크기이다.

import sys
input = sys.stdin.readline

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

for i in range(n):
    t = int(input())
    for j in range(t, k+1):
        dp[j] = min(dp[j], dp[j-t]+1)

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

Written by@hyesungoh
Learning every moment

InstagramGitHubLinkedIn