[ 백준 2294번 ] 동전2 파이썬

---

[백준 2294번 동전2 바로가기]

2294번: 동전 2

논리

1. 주어진 동전 중복 제거
2. target에서 각 동전을 빼는 방법으로 bfs 탐색
3. target이 0이 되는 경우 반환(target이 음수가 되는 경우 무시)
4. 모든 경우를 탐색해도 target이 0이 되는 경우가 없으면 -1 반환

코드

import sys
from collections import deque, defaultdict

# using BFS + 중간 기록
def minimum_coins():

    ################################################
    # inputs
    n, k = list(map(int, sys.stdin.readline().split()))
    coins = [None] * n
    for i in range(n):
        coins[i] = int(sys.stdin.readline())
    coins = sorted(set(coins), reverse=True)
    ################################################

    queue = deque([(0, k)])
    visited = defaultdict(lambda: False

# print(minimum_coins())

다른 풀이

코드 (다른 분)

# using dynamic programming: others code
def minimum_coins2():
    # inputs 
    N, K = map(int, sys.stdin.readline().split())
    coins = sorted(set([int(sys.stdin.readline()) for _ in range(N)]))

    min_coins = [sys.maxsize] * (K+1) # min_coins[target] : target을 만들수 있는 최소 동전의 개수
    min_coins[0] = 0                  # min_coins[0]: 0원을 만들수 있는 최소 동전의 개수: 0

    for coin in coins:                  # 작은 코인부터
        for target in range(coin, K+1): # 코인 이상의 target 모두 확인: target-coin에서 동전 1개(coin)만 더하면 target이 됨을 이용
            min_coins[target] = min(min_coins[target], min_coins[target-coin] + 1)

    return min_coins[K] if min_coins[K] != sys.maxsize else -1

print(minimum_coins2())