[백준 2024/09/23] 2294번 동전 2

1. 문제

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

2. 접근 방법

처음에는 bfs를 이용해서 coin의 개수를 1개씩 늘려가면서, 만약 합이 k인 경우가 나온다면, 이를 반환하는 코드를 작성했었다.

이런식으로 bfs 코드를 구상하고 작성하였다.

 

from collections import deque

def get_min_coin():
    c_cnt = 0
    visited = []
    while bfs:
        c_cnt += 1
        coin_length = len(bfs)

        for _ in range(coin_length):
            coin_popped = bfs.popleft()
            if coin_popped in visited:
                continue
            visited.append(coin_popped)
            for c in coins:
                if coin_popped + c == k:
                    return c_cnt + 1
                elif coin_popped + c < k:
                    bfs.append(coin_popped + c)

    return -1


if __name__ == "__main__":
    n, k = map(int, input().split())
    coins = set()
    bfs = deque()
    for _ in range(n):
        coins.add(int(input()))

    for c in coins:
        bfs.append(c)

    print(get_min_coin())

이런식으로 작성하였으나, 시간 초과가 발생하여 다른 접근을 요한다는 것을 알게 되었다.

 

고민을 하다가 dijkstra를 이용하여 풀어보기로 하였다.

cost로 [sys.maxsize]를 가지는 리스트를 형성하고, dq에 (동전의 합, 동전 개수)로 넣어주어 시작하였다.

 

처음에는 dq.append((0, 0))으로 두었고, pop 할 때마다 받아둔, n가지 종류의 동전을 for 문을 돌았다.

 

예를 들어서 설명을 시작해 보도록 하겠다.

3 15
1
5
12

백준 예시와 동일하게 15원을 목표로 하고 있고, 1원 5원 12원이 있다고 가정하자.

 

처음에는 (0원, 0개) 를 pop 하게 된다.

for (1원, 5원, 12원 ) 을 돌 때, 

0원 + 1원 = 1원이 되게 된다.

costs[1원] = INF가 저장되어 있고, costs[1원] > 0개 + 1개(1원 추가) 보다 크므로, update를 진행하여 준다.

따라서, costs[1원] = 0개 + 1개 가 저장되게 된다.

 

costs[1원]이 update 되었기 때문에 1원으로부터 파생할 수 있는 1원 + 1원, 1원 + 5원, 1원 + 12원도 다시 고려해 주어야 한다.

따라서, dp.append((1원, 1개))를 넣어주고, while 문 반복을 통한 for문을 통해 1원 + 1원, 1원 + 5원, 1원 + 12원에 대한 고려도 다시 진행되게 된다.

 

마지막으로 k원이 update 안되는 경우도 고려해 주어야 한다.

만약 costs[-1] 이 k 원 보다 크다면, INF가 저장되어 있는 경우이므로, -1을 print 해주었다.

 

위 예제에 대한 costs를 최종적으로 출력해 보았다.

[0, 1, 2, 3, 4, 1, 2, 3, 4, 5, 2, 3, 1, 2, 3, 3]

0원에 대해서 0개의 동전, 

1원에 ... 1개

2원 ... 2개 

...

15원 3개의 동전으로 최소 동전을 이용할 수 있다.

 

원래 dijkstra를 배울 때, 특정 도시로부터 다른 도시까지의 최단 거리들을 구하기 위해 사용된다고 알고 있다.

하지만, 이와 같이 도시가 아니라

여러 동전의 개수 조합을 통해 특정 k원을 구할 때도 유용하다는 것을 알 수 있었다.

즉, 동전의 개수 조합이, 여러 route에 상응하게 되는 것이다. 또한, 동전의 개수의 합이 도시에 상응되게 되는 것이다.

이를 그림으로 표현해 보았다.

 

12원을 main으로 보게 되면, 0원에서 12원에 1개의 동전으로 도달할 수 있다.

다른 방법으로는 5월 10원 11원을 거쳐서 12원에도 도달할 수 있다. 하지만 1개의 동전으로 12원에 도달하는 것이 cost가 더 저렴하므로 update할 필요가 없게 되고, dq에 들어가서 주변 도시들에 대해서 update를 안해주게 된다.

 

이전에 2665번 미로 만들기의 경우에도 dijkstra를 이용하여 풀었었다. (0-1 BFS) 이 또한, 각각의 idx가 도시가 되고 검은색 방에 갈 때마다 1원을 소요하고, 이를 이전에 저장된 cost와 비교하여 더 저렴하다면 수정하게 된다.

 

3. 코드

import sys
from collections import deque


if __name__ == "__main__":
    n, k = map(int, input().split())
    coins = set()
    dq = deque()

    for i in range(n):
        coins.add(int(input()))

    coins = list(coins)

    costs = [sys.maxsize] * (k+1)
    costs[0] = 0

    dq.append((0, 0))

    while dq:
        cost, n_coins = dq.popleft()

        for i in range(len(coins)):
            new_c = cost + coins[i]
            if new_c > k:
                continue
            if costs[new_c] > n_coins + 1:
                costs[new_c] = n_coins + 1
                dq.append((new_c, n_coins + 1))

    if costs[-1] > k:
        print(-1)
    else:
        print(costs[-1])