BFS : 동전 2(백준 2294번)

▶ 문제 : https://www.acmicpc.net/problem/2294

2294번: 동전 2

##### 문제 #####
# n가지 종류의 동전이 있다. 
# 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 
# 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 
# 각각의 동전은 몇 개라도 사용할 수 있다.
# 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

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

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

 

▶ 접근 방법

최단 거리를 찾는 과정과 유사하게 문제를 해결하고자 하였다.
목표 금액을 만들기 위해 동전 세트에서 동전을 하나 씩 꺼내는 과정을 반복한다.
동전을 하나 씩 늘려가며 만든 금액과 목표 금액을 비교함으로써 최소 개수를 보장하고자 하였다.

 

▶ 풀이 코드

import sys
from collections import deque

# 전체 동전의 수와 목표 금액을 입력 받는다.
coin_num, target_won = map(int, sys.stdin.readline().split())

# 동전 종류를 입력 받는다.
# 세트를 사용하는 이유는 가치가 같은 동전이 여러 번 주어질 수 있기 때문이다.
coin_set = set(int(sys.stdin.readline()) for _ in range(coin_num))
# print(coin_set)

# 동전 사용 여부를 표시해준다.
check_coin = [0 for _ in range(target_won + 1)]
# print(check_coin)

queue = deque()
# 동전 세트에서 동전을 하나씩 꺼낸다.
for coin in coin_set:
    # 꺼낸 동전이 목표 금액보다 크면 패스
    if coin > target_won :
        continue
    # 아니라면, 해당 동전을 queue에 넣어준다.
    queue.append([coin, 1])
    # 그리고 해당 동전 사용 여부를 표시해준다.
    check_coin[coin] = 1

result = -1
while queue:
    # queue에서 현재 동전 금액과 해당 금액을 만들기 위해 사용한 동전 개수를 뽑는다.
    current_coin, count = queue.popleft()
    # 현재 동전 금액이 목표 금액과 같다면
    if current_coin == target_won:
        # 사용한 동전 개수를 출력한다.
        print(count)
        result = 0
        break
    # 동전 세트에서 동전을 하나 씩 다시 꺼낸다.
    for coin in coin_set:
        # 현재 동전 금액에 꺼낸 동전을 더한 금액이 목표 금액보다 크면 패스
        if current_coin + coin > target_won:
            continue
        # 현재 동전 금액에 꺼낸 동전을 더한 금액이 처음 나온 조합이라면
        if check_coin[current_coin+coin] == 0:
            # 사용 여부를 표시해주고
            check_coin[current_coin+coin] = 1
            # target_won을 만들 수 있는 후보 조합으로서 queue에 넣어준다.
            queue.append([current_coin+coin, count + 1])

if result:
    print(result)

 

▶ 관련 링크

2021.11.18 - [알고리즘] - BFS(Breadth First Search, 너비 우선 검색)이란?

2021.11.19 - [알고리즘] - 그래프(Graph)란?

2021.11.19 - [알고리즘] - BFS : 미로 탐색(백준 2178번)

2021.11.19 - [알고리즘] - BFS : 특정 거리의 도시 찾기(백준 18352번)

2021.11.19 - [알고리즘] - 다익스트라 알고리즘(Dijkstra Algorithm)이란?

2021.11.19 - [알고리즘] - BFS : 최소비용 구하기(백준 1916번)

2021.11.20 - [알고리즘] - BFS : 미로만들기(백준 2665번)

2021.11.20 - [알고리즘] - BFS : 탈출(백준 3055번)