[백준 2294 골5] 동전2 (dp/python) -/3R

https://www.acmicpc.net/problem/2294

로직

만약 k원짜리 동전이 있다면 dp(k)=1로 세팅
그렇지 않다면 동전 지불 개수 세는 로직처럼 dp(coin)+dp(i-coin)으로 갱신하고 기존 dp 값과 비교
그 후 작은 것을 선택
이 때 dp 디폴트값은 max value인 10001로 둔다.

소스코드

import sys
input = sys.stdin.readline

def makedp():
    for i in range(1, k+1):
        if i in coins: dp[i] = 1
        for coin in coins:
            if i > coin:
                dp[i] = min(dp[coin]+dp[i-coin], dp[i])
    # print(dp)
    
if __name__ == "__main__":
    n, k = map(int, input().split())
    coins = []
    for _ in range(n):
        coins.append(int(input()))
    max_coin = max(coins)
    coins = set(sorted(coins))
    dp = [10001 for _ in range(k+1)]
    makedp()
    if dp[k] == 10001: print(-1)
    else: print(dp[k])

기타

1. 일단 기본적으로 이정도 난이도는 쉽게 풀 수 있었다.
2. 그러나 dp의 디폴트를 아무 생각 없이 0으로 뒀다가 디버깅했고 문제를 읽을때 이 점을 주의하는게 좋을듯