[백준][python]2294 동전2

문제

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

소스코드

import sys

if __name__ == "__main__":
    n,k = map(int,input().split())
    coin = [int(input()) for _ in range(n)]
    dp = [10001] * (k+1)
    dp[0] = 0

    for c in coin:
        for i in range(c,k+1):
            dp[i] = min(dp[i],dp[i-c]+1)
    print(-1 if dp[k]==10001 else dp[k])

 

후기

DP 문제이다. bottom-up 방식을 이용하여 작은 값을 이루는 동전의 최소값을 메모이제이션해준다.

동전1 문제와 마찬가지로 주어진 동전을 기준으로 반복문을 돌려 값을 체크해준다.

 

최소값을 구하는 문제이므로 기존 dp 를 10001 로 초기화 한 후 min 값을 구해야한다.

주어진 조건 K의 최대값은 10000 이다. 즉 1을 10000 한 값이 최대값이므로 그 이상의 값인 10001로 초기화해준다 (나올수가 없는 값)

그리고 문제를 잘 ~ 읽어서 불가능하면 -1 이걸 꼭 체크해라 처음에 체크 안해서 틀렸다 ㅠㅠ