[백준 2294 / Python] 동전 2

동전 2

🔍 알고리즘 분류

• DP

💡 문제 풀이

1. dp 배열을 k+1만큼 생성 후 모두 최댓값으로 초기화
2. dp[0]=0으로 초기화
3. 가치를 1부터 탐색하며 이전 가치에서 동전을 하나 추가했을때 최솟값 찾아서 갱신

📄 코드

• Python

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
coins = []
dp = [10001] * (k + 1)
dp[0] = 0

for _ in range(n):
    coin = int(input())
    coins.append(coin)


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

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

• 시간복잡도: O(NK)