t_효율적인화폐구성_228

문제

화폐를 최소한으로 사용해서 합을 M이 되도록함
만약 만들 수 없으면 -1, 몇번쓰는지 print

답

이전에 말했드시 좀더 작은 값이 큰값의 배수가 아니므로 그리디로 풀 수 없다.

input = input.strip().split('\n')

n,m = map(int,input[0].split())
arr = []
ans = -1
for i in range(1,len(input)):
    v = int(input[i])
    if v == m:
        ans = 1
    arr.append(v)

q = deque(list(map(lambda x:[x,1],arr)))
while len(q) > 0 and ans == -1:
    v, step = q.popleft()
    for a in arr:
        tmp = v + a
        if tmp == m:
            ans = step+1
            break
        elif tmp < m:
            q.append([tmp,step+1])

print(ans)