2294번 파이썬

이 문제는 현재 가격에(num)에 동전 종류에 따른 가격(i) 를 더해서 현재 p[num+i]에 저장되어있는 값보다 p[num]+1이 작으면 그 값으로 치환하는 방식을 이용했다.

p값을 10001로 치환해준 이유는 k의 최댓값이 10000이며 10000인 경우도 존재할 수 있기 때문에 10001로 설정했다.

그리고 이 문제는 경우의 수가 아니고 최소 동전 개수를 구하는 문제기 때문에 문제를 잘 읽어보고 풀어야한다!!

import sys
input = sys.stdin.readline
n,k = map(int,input().split())
ary = [int(input()) for _ in range(n)]
p = [10001 for _ in range(k+1)]
p[0]=0
for num in range(0,k+1):
  for i in ary:
    if (num+i)<(k+1):
        p[num+i] = min(p[num+i],p[num]+1)
if p[k]==10001:
  print(-1)
else:
  print(p[k])