python 백준 2294 동전2

백준 2294번 문제

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

2294번: 동전 2

1. 이것을 이제 python으로 bfs를 이용하여 구현하면 이렇다

from collections import deque
import sys
#sys.stdin = open('inputs.text')

n, target = map(int, sys.stdin.readline().split())
check_list = [0 for _ in range(target+1)]
### 8~10번 줄을 11번줄로 한줄로 쓸수 있다.##
# coins = []
# for _ in range(n):
#     coins = coins + list(map(int,sys.stdin.readline().split()))
coins = set(list(int(sys.stdin.readline()) for _ in range(n)))

stable = True
queue = deque()

for coin in coins:
    if coin == target:
        stable == False
        print(1)
        break
    elif coin < target:
    ## 코인의 값과 count 1을 리스트에 넣고 queue에 넣어 준다 ##
        queue.append([coin,1])
        check_list[coin] = 1

while queue:
    value, cnt = queue.popleft()
    if value == target:
    ## 서치가 target을 찾았다면 더 이상 bfs를 할 필요가 없기때문에 break를 걸고 찾았다고 알려준다 ##
        stable = False
        print(cnt)
        break
    for coin in coins:
        if coin+value <= target and check_list[coin+value] == 0:
            check_list[coin+value] = 1
            queue.append([value+coin,cnt+1])

if stable:
    print(-1)

2. 다이나믹 프로그래밍을 이용하여 구현하는 방법도 있다 이것은 추후 업데이트 예정