[BOJ]2294. 동전2

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

2294번: 동전 2

 

문제

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

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

입력

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

출력

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

 

풀이

dp로 푸는 방법과 bfs로 푸는 방법이 있는 것 같다. dp는 학습후에 재도전해보자!

 

bfs

1. 맨 처음 코인들의 값을 (coin, 1)로 큐에 저장한다 (coin을 만드는 최소 count는 1이므로)

2. queue에서 한개씩 뽑아서 (popleft) 다른 코인의 값을 더해본다.

3. 더한 new_coin의 값이 목표인 k보다 작고, 현재 기록중이 최소 코인의 개수보다 작다면 다시 queue에 넣는다!! (아직 k가 되지 않았으니까)

4. 만약 new_coin의 값이 k와 같다면, min_count 값과 현재 count + 1을 비교해서 작은 값을 채택한다.

 

코드

import sys
import collections

n, k = map(int, sys.stdin.readline().strip().split())

coin_list = []

for _ in range(n):
    coin_list.append(int(sys.stdin.readline().strip()))

coin_list.sort()

# (더해진 코인의 값, 더한 코인의 개수)를 저장할 queue 생성!
queue = collections.deque()
for coin in coin_list:
    queue.append((coin, 1))

# 코인의 값을 방문했다고 체크하기 위한 visited (예를 들어, 5는 (5, 1)도 가능하고 1코인 5개로 (5, 5)도 가능하다. 이를 막기 위해 visited 사용!)
visited = [0] * 10001
max_coin = max(coin_list)
min_count = 10001
while queue:
    now_coin, count = queue.popleft()

    for i in range(n):
        new_coin = now_coin + coin_list[i]

        # 더해진 코인의 값이 목표인 k보다 크다면 반복문 stop!
        if new_coin > k:
            break

        # queue에서 일찍 나오는 값이 count가 작다. 때문에 visited에 기록해두고 같은 값을 가질 때는 queue에 저장하지 않는다.
        if visited[new_coin] == 1:
            continue

        # 더해진 코인의 값이 목표인 k보다 작고, 현재 최소 coin의 개수인 min_count 보다 작다면 queue에 넣는다!
        if new_coin < k and count + 1 < min_count:
            visited[new_coin] = 1
            queue.append((new_coin, count + 1))
        elif new_coin == k:
            min_count = min(min_count, count + 1)

if min_count == 10001:
    min_count = -1
print(min_count)