동전 2 (BFS)

문제

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

 

입력

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

 

출력

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

 

예제 입력 1

3 15
1
5
12

예제 출력 1

3

 

- 문제 해결

처음엔 아이디어 생각을 전혀 하질 못했었다.

그냥 동전 하나를 1개 넣고 다음 동전의 재귀를 돌린 후, 다시 동전 넣은 것을 더하고 즉,

위 그림의 예제라면

재귀(10) - 1개 ~ 2개
재귀(6) - 1개 ~ 3개
재귀(4) - 1개 ~ 5개

                                      10                                           10(2개)
              6(1개)                6(2개)              6(3개)
4(1개) 4(2개) 4(3개) 4(4개) 4(5개)

 

'이런 느낌으로 들어가지 않을까?' 이렇게 아이디어를 내고 하니 전혀 감을 못잡겠고 풀리지도 않았다.

그래서 힌트를 받아 처음 작성한 해결방식대로 반대로 돌아가며 문제를 풀었는데, 실수한 부분을 전혀 찾지 못하고 결국엔 문제를 제대로 풀질 못했다.

- 팀원에게 도움받아서 푼 방식

import sys
from collections import deque

input = sys.stdin.readline

n, target = map(int, input().split())

coins = set()

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

coins = list(coins)
coins.sort()

queue = deque()
queue.append(0)
visited = set()


coin_cnt = 0
while queue:

    length = len(queue)
    flag = False

    for _ in range(length):
        coin = queue.popleft()
        for c in coins:
            if coin + c in visited:
                continue
            if coin + c < target:
                queue.append(coin + c)
                visited.add(coin + c)
            elif coin + c == target:
                flag = True
                break
        if flag:
            break
    coin_cnt += 1
    if flag:
        break

    if not queue:
        if not flag:
            coin_cnt = -1

print(coin_cnt)

근데 BFS로 풀 때, 이것보다 더욱 간단하게 표현이 가능하다고 한다. (아직 생각은 안해봤음)

그리고 DP로도 풀 수 있다는데

아이디어만 말해보자면, [1, 2, 3, 4, 5, 결과] 현재 이것은 [4, 8, 12, 16, 20] 이렇게 되어있는데,

12는 6을 2개로 만들 수 있으므로 결과값까지 가는 길 중에 겹치는 부분이 있으면 동전 개수의 최솟값 비교를 통해 도달했을 때의 동전의 최솟값을 구하는 방식이라고 한다. ('머리로만 이해해도 되겠지?' 는 절대 아니고 담에 기억이 안날 때 한번 더 풀어볼 예정이다.)