kt_효율적인 화패 구성

문제

어떤 나라에는 가치가 서로 다른 N가지 동전이 있습니다. 이 동전들을 이용해서 가치의 합이 M이 되게 하는 동전 개수의 최솟값을 구하는 프로그램을 작성하세요. 예를 들어 가치가 2, 3인 단위의 동전이 있을 때는 가치 15를 만들기 위해 가치 3짜리 동전 5개를 사용하는 것이 동전의 개수가 가장 최소가 됩니다.

그리디 5원3원가정

답

coin 인덱스가 무게를 넘을지를 생각하지 못햇다. ㅋㅋ

import sys 
from collections import deque
input = sys.stdin.readline

def solve():
    n,m = map(int,input().strip().split())
    arr = [10001] * (m + 1)
    coin = []
    for _ in range(n):
        k = int(input().strip())
        if k == m: return 1
        if k > m : continue
        arr[k] = 1
        coin.append(k)
        
    for i in range(m+1):
        if arr[i] != 0 :
            for c in coin:
                ni = i + c
                if ni<=m:
                    arr[ni] = min(arr[ni],arr[i]+1)
    return arr[m] if arr[m]<10001 else -1
    
print(solve())

import sys 
from collections import deque
input = sys.stdin.readline

def solve():
    n,m = map(int,input().strip().split())
    coins = []
    for _ in range(n):
        k = int(input().strip())
        if k == m: return 1
        if k > m : continue
        coins.append(k)
        
    q = deque(list(map(lambda x:(x,1),coins)))
    while len(q) > 0:
        v, step = q.popleft()
        for a in coins:
            tmp = v + a
            if tmp == m:
                return step+1
            elif tmp < m:
                q.append((tmp,step+1))
    return -1
    
print(solve())
    ```

```python
import sys 
from collections import deque
input = sys.stdin.readline

def solve():
    n,m = map(int,input().strip().split())
    coins = []
    visited = set()
    for _ in range(n):
        k = int(input().strip())
        if k == m: return 1
        if k > m : continue
        coins.append(k)
        visited.add(k)
    q = deque(list(map(lambda x:(x,1),coins)))
    
    # print(q)
    while len(q) > 0:
        v, step = q.popleft()
        # print(q)
        for a in coins:
            tmp = v + a
            if tmp in visited:
                continue
            if tmp == m:
                return step+1
            elif tmp < m:
                visited.add(tmp)
                q.append((tmp,step+1))
                
    return -1
    
print(solve())