백준 / 골드 5 / 2294. 동전 2

여기서 동전이 이런 동전은 아니겠죠? 호호

생각해봅시다!

• 시간제한이 1초에 추가 시간 없음이라, 예사롭지 않은 방법으로 풀어야겠군요.
• 꼭 BFS로 그래프만 탐색할 수 있는 건 아닙니다.
• 노드를 현재 금액으로, 간선을 해당 금액에 동전 하나를 더하는 행위로 생각해봅시다.
  • 모든 노드에는 선택할 수 있는 동전만큼 간선이 연결되어 있다고 볼 수 있습니다.
  • 예를 들어, 1원, 5원, 12원 동전으로 15원을 만드는 문제에선, 각 노드에 1원 / 5원 / 12원을 더하는 간선이 각각 연결되어 있다고 생각하면 됩니다.

결국엔 BFS문제라고?

• BF는 0원을 뜻하는 루트 노드부터 시작하고, 간선에 따라 동전을 하나씩 추가하며 탐색을 진행합니다.
• 이때 이동한 간선 수는, 사용한 동전의 개수가 됩니다.
• BFS는 루트 노드에서 가까운 노드부터 방문하므로, 특정 노드까지의 최소 이동 거리를 구하는 데 적절합니다.
  • 즉 원하는 금액에 도달하기 위한 최소 동전 개수를 구할 때도 사용할 수 있습니다.
• 즉 목표 금액에 도달할 때까지 BFS를 수행하고, 그때까지 이동한 간선 수를 세면, 최소한으로 필요한 동전의 개수를 알 수 있습니다.

풀이

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

N, K = map(int, input().split())	# 동전 단위 수, 목표 금액
coins = []          # 사용 가능한 동전 단위
for _ in range(N):
    coins.append(int(input()))

def bfs(K, coins):
    # K원을 만들 때 필요한 동전의 최소 개수
    # 아직 방문하지 않은 경우 None
    answer = [None] * (K + 1)
    answer[0] = 0

    # 현재 금액, 동전 수
    queue = deque([0])

    while queue:
        # 현재 금액: now
        now = queue.popleft()

        # 현재 금액에 각 동전의 금액 추가
        for c in coins:
            after = now + c

            # 목표 금액 K원을 안 넘겼는지 확인
            # 아직 확인하지 않은 금액인지 확인
            if after <= K and answer[after] is None:
                queue.append(after)

                # 현재 금액에 동전을 한 개 추가했으니...
                answer[after] = answer[now] + 1
                
                # 목표 금액을 찾은 경우
                if after == K:
                    return answer[after]
                
    # 목표 금액을 찾지 못한 경우
    return -1

print(bfs(K, coins))

BFS 준비

• 결국엔 BFS와 유사하게 구현할 거니 deque 자료구조인 queue를 만들어줍니다.
  • 루트 노드에 해당하는 값 0을 넣어줍니다.
• answer는 리스트로 각 금액에 도달하는 데 필요한 최소 동전 수를 저장합니다.
  • answer[i]는 금액 i를 만들기 위해 필요한 최소 동전 수를 뜻합니다.
  • answer[0]는, 0원을 만들 땐 동전이 필요없으니 0으로 초기화합니다.
  • 나머지 값은 None으로 초기화해 아직 방문하지 않았음을 표시합니다.

BFS 수행

• 큐에서 꺼낸 현재 금액 (now)에 대해, 각 동전 금액(c)을 더한 결과(after)를 계산합니다.
  • 이때 계산된 금액(after)이 목표금액인 K원보다 작거나 같고, 아직 방문하지 않은 경우 (if answer[after] is None)에만 큐에 추가합니다.
  • 이미 방문한 경우, 똑같은 아니면 더 적은 동전 개수로 해당 금액을 완성할 수 있다는 소리니까, 체크하는 의미가 없겠죠.
• 큐에 추가한 이후, 금액 after은 현재 금액보다 동전을 1개 더 사용해 만들 수 있으므로, answer[after] = answer[now] + 1로 저장합니다.
• 목표 금액 K에 도달한 경우, answer[after]를 반환하면 정답입니다.
• queue가 빌 때까지 목표 금액을 만들지 못한 경우-1을 반환합니다.

시간 복잡도

• 목표가 K원일 때, 최대 1원부터 K원까지 모든 경우를 탐색하므로, $O(K)$
  • $K \leq 10,000$이므로 시간제한 1초만에 통과 가능

기억할 점

• 제일 '적은' '빠른' '가까운' 경우를 찾는 문제는 BFS로 빠르게 풀 수 있을 지도 모른다