[Gold V] 동전 2 - 2294 (BFS, DP)

[Gold V] 동전 2 - 2294

문제 링크

성능 요약

메모리: 34112 KB, 시간: 236 ms

분류

다이나믹 프로그래밍(dp)

문제 설명

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

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

입력

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

출력

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

풀이방법 (풀이 시간 : 20분)

보통 실버2~골드 이상 등급의 최소 ~개수를 구하는 문제는 완탐 등을 이용해서 풀면 시간초과가 나기에 DP 혹은 BFS 알고리즘을 통해서 문제를 해결해야한다. 나는 대충 그려보고 나니 BFS라고 생각하여 그렇게 문제를 풀게 되었다. 

1. 동전을 사용한 최소 개수를 담기위해 배열을 k+1개(graph) 만큼 만들었다.+1개를 한 이유는 배열은 0번 인덱스부터 시작하기에 인덱스를 헷갈리지 않기 위해서 + bfs를 돌리기 전에 큐에 0을 넣고 시작할 수 있어서다.

2. while문을 통해 bfs를 돌리면서 도달할 때마다 이전의 값보다 1을 더하여 동전의 가치 1부터 k까지 각 graph 인덱스에 최소 몇 번만에 동전을 사용하여 동전의 가치에 맞는지 알 수 있다.

3. bfs로 모두 탐색한 뒤, 해당 인덱스(k)에 값이 들어와있지 않고 0이라면 정답을 구할 수 없는 문제이므로 -1을 출력하고 그 외에는 그대로 출력해주면 해결.

느낀점

골드 문제라 그럴리는 없다 생각했지만, 처음에 문제를 잘못 이해하여 그냥 반복문으로 풀린다고 착각하고 내림차순으로 정렬하여 제일 큰 동전의 가치부터 차례대로 계산했지만, 출력값이 제대로 나오지 않아 문제를 다시보니 k보다 작은 가치의 동전 중 가장 높은 동전이 아니고 더 낮은 가치로 k를 최소 횟수로 맞출 수 있다는 사실을 깨달았다.

문제를 제대로 이해한 뒤 어떠한 알고리즘을 사용해야할지 종이와 펜으로 그려보았고, BFS를 사용해야겠다는 판단이 나왔고, 금방 풀 수 있었다. 해당 문제의 정답률이 20%대인 것에 비해 은근히 쉽게 풀렸다. 그런데 알고리즘 분류를 보니 DP 알고리즘 사용이었다. 아마도 DP는 코드는 짧지만 구현하기가 꽤 까다로워 성공률이 낮은 듯 하다. 

그래도 BFS로도 풀린다는 점.!

from collections import deque
n, k = map(int,input().split())
dx = set()
for i in range(n):
    dx.add(int(input()))
dx = list(dx)

graph = [0 for _ in range(k+1)] 

q = deque()
q.append(0)
graph[0] = 0
while q:
    x = q.popleft()
    if x == k:
        break
    for i in range(len(dx)):
        nx = dx[i] + x
        if 0 < nx <= k and graph[nx] == 0:
            graph[nx] = graph[x] + 1
            q.append(nx)
if graph[k] == 0:
    print(-1)
else:
    print(graph[k])