[테스트케이스 추가] 백준 2294 동전2 python, 파이썬

1. 문제

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

2294번: 동전 2

 

 

 

 

2. 풀이

입력되는 동전의 길이가 많이 길이 않아서 동전 전체를 돌면서 확인해보면 되는 문제

 

 

 

3. 구현

import sys
import math

# sys.stdin=open('input.txt')

n,k = map(int, sys.stdin.readline().split())
coins=[]
while n:
    n-=1
    c = int(sys.stdin.readline())
    coins.append(c)
coins.sort()

mm=[math.inf]*int(k+2)
mm[0]=0

for i in range(k+1):
    for j in coins:
        if i<j:
            break
        mm[i]=min(mm[i],mm[i-j]+1)

if mm[k]==math.inf:
    print(-1)
else:
    print(mm[k])

 

 

 

 

4.테스트케이스 추가

18 52
25
15 
17 
14
8 
30 
27 
11 
20 
6 
13 
13 
8 
9 
19 
15 
29 
30

답: 2

 

8 17
13
1 
10 
11 
1 
8
14 
12

답: 3