[PY] 2294 : 동전 2

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

처음부터 끝까지 내가 했다면 정말 좋았겠지만, 아쉽게도 아이디어가 아예 안떠올랐기에 파일럿 코의 도움을 받았다.
이정도..

 

• 큐(queue)에 시작 상태(금액 0, 동전 수 0)를 삽입합니다.
• 현재 상태에서 가능한 모든 동전 값을 더하여 다음 상태를 큐에 추가합니다.
• 방문 여부를 체크하여 중복 계산을 방지합니다.
• 목표 금액에 도달하면 탐색을 종료하고 해당 경로의 동전 수를 반환합니다.

BFS로 일리 있는 구간의 탐색을 진행 할 수 있다는 것에 또 한번 놀란다.
이걸 BFS라고 부르는 이유는 queue를 사용하기 때문 딱 하나일 것이다.

메모리 초과 이슈로 인해 visited 부분도 도움을 좀 받았다. 그러고 나니 말끔하게 해결

 

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

coinList = []
queue = deque()
minCoinCnt = float('inf')



coinCnt, req = map(int, input().split())
visited = [float('inf')] * (req + 1)  # 최소 동전 수를 추적
visited[0] = 0  # 초기 상태

coinList.sort()

for i in range(coinCnt):
    inputVal = int(input())
    coinList.append(inputVal)
# means : coin total value | total coin count.
queue.append([0, 0])
def BFS():
    global minCoinCnt
    while queue:
        coinTotalVal, coinTotalCnt = queue.popleft()

        if(coinTotalVal == req):
            minCoinCnt = min(coinTotalCnt, minCoinCnt)
            continue
        elif (coinTotalVal > req):
            continue
        else:
            for coin in coinList:
                nextVal = coinTotalVal + coin
                if nextVal <= req and coinTotalCnt + 1 < visited[nextVal]:
                    visited[nextVal] = coinTotalCnt + 1
                    queue.append([nextVal, coinTotalCnt + 1])
BFS()
if (minCoinCnt != float('inf')):
    print(minCoinCnt)
else:
    print('-1')