[백준] 동전 2

거북이·2023년 3월 31일
0

백준[골드5]

목록 보기
44/82
post-thumbnail

💡문제접근

  • 이전에 포스팅했던 [[백준] 2293번 동전 1]의 문제와는 다른 문제였다. 이 문제는 k원의 가치를 만드는데 필요한 동전의 개수가 최소가 되게끔 하는 문제였다.

💡코드(메모리 : 31256KB, 시간 : 404ms)

import sys
input = sys.stdin.readline

n, k = map(int, input().strip().split())
coins = []
for i in range(n):
    coins.append(int(input()))

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

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

💡소요시간 : 24m

0개의 댓글