[백준 2294] 동전 2 (골드 5) Python

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

2294번: 동전 2

---

문제

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

출력

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

---

풀이 방법

합이 k원이 되도록 하는 동전의 최소 개수를 구하는 문제이다. bfs를 이용해서 k가 되기 위한 최소 경로를 구한다.

# 백준 2294 동전 2
# 동전의 개수를 최소화하면서 합이 k원이 되도록 하는 동전 최소 개수
# 불가능하면 -1

from collections import deque
n, k = map(int, input().split())
coins = set()

# 입력 받기. 
for _ in range(n):
    tmp = int(input())
    # k보다 큰 동전은 필요 없으므로 입력을 받을 때 제외.
    if tmp > k: 
        continue
    # k와 동일한 동전이 있다면 해당 동전만 사용하면 되므로 1을 출력하고 종료.
    elif tmp == k: 
        print(1)
        exit()
    else:
        coins.add(tmp)

coins = sorted(list(coins), reverse=True)
visited = [0] * (k+1)
# bfs
def bfs(start):
    q = deque(start)
    while q:
        node = q.popleft()
        if node == k:
            break
        
        for c in coins:
            if node + c > k:
                continue
            if visited[node+c] == 0:
                visited[node+c] += visited[node] + 1
                q.append(node+c)

bfs(coins)

if visited[k] != 0:
    print(visited[k]+1)
else:
    print(-1)

  입력 받는 부분을 다소 길게 작성하였다. k보다 큰 동전은 필요 없으므로 입력 받지 않았고, 입력값이 k와 같으면 동전을 1개만 쓰면 되므로 곧바로 1을 리턴하도록 하였다.

  bfs로 순환할 때 값이 큰 동전부터 확인하도록 coins를 내림차순으로 정렬해주었다. visited 배열은 인덱스가 노드를, 배열에 저장되는 값은 그 노드까지 가는 경로의 길이를 나타낸다. 

  bfs 함수에서는 현재 확인 중인 node에 각 동전의 값 c를 더해준 뒤, node+c을 아직 방문하지 않았다면 node+c로 가는 경로의 수에 1을 더해주면서 경로 길이를 기록하도록 하였다.

  bfs가 종료되면 visited[k]를 출력하였다. 이때 visited[k]에 1을 더해준 까닭은 최초로 사용한 동전의 값으로 가기 위한 경로의 수 1을 아직 더해주지 않았기 때문이다. 

  만약 visited[k]가 0이면 k 값을 만들 수 있는 방법이 없는 것이므로 -1를 출력해주었다.