[백준/DP] 2294번: 동전 2

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

2294번: 동전 2

 

1. 반복문을 통해 사용 가능한 동전들을 꺼냅니다.

2. 사용 가능한 동전부터 원하는 숫자(k)까지 반복문을 통해, 해당 숫자를 맞추기 위해 동전을 사용하는 가장 적은 횟수를 확인합니다.

 

import sys

input = sys.stdin.readline

n,k = map(int,input().split())

coins = [int(input()) for _ in range(n)]
coins.sort()

dp = [10001] * (k+1)
dp[0] = 0

# 사용 가능한 코인들만 확인
for coin in coins: 
	# coin 부터 구하려는 숫자까지 확인
    for i in range(coin,k+1):
        dp[i] = min(dp[i], dp[i-coin]+1)
if dp[k]== 10001: print(-1)
else: print(dp[k])