백준 2294
- n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.
- 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.
- 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.
- 첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.
입출력
| 입력 | 출력 |
|---|---|
| 3 15 1 5 12 | 3 |
접근 방식
: 동전의 개수를 최소로 하며 가치가 k가 되도록 만드는 것이므로 bfs로 풀 수 있다.
주의할 점
- 가치가 같은 동전이 여러 번 주어질 수 있으므로 동전 집합을 만들어 중복 허용 x
- 각각의 동전을 하나씩 사용하는 것이 초기 상태이므로 k이하인 동전을 모두 큐에 넣고 방문처리
- 큐에서 하나씩 원소를 빼서 동전들에 대해 연산. 조건에 맞으면 큐에 넣고 카운트 업
알게된 점
dp를 이용해서 풀 수 있음.
dp의 각 수는 매우 큰 수인 1e9로 초기화, dp[0] = 0.
입력받은 코인에 대해서,
dp[i번째-코인]+1과 dp를 비교해서 저장.
dp는 점화식 떠올리는게 정말 어려운 것 같다..
코드
bfs로 풀기
from collections import deque
import sys
def bfs():
while q:
x = q.popleft()
if x == k:
return visited[x]
for c in coin:
nx = x + c
if nx <= k:
if visited[nx] == 0:
visited[nx] = visited[x]+1
q.append(nx)
return -1
n, k = map(int, sys.stdin.readline().split())
coin = {int(sys.stdin.readline()) for _ in range(n)}
visited = [0]*(k+1)
q = deque()
for c in coin:
if c <= k:
q.append(c)
visited[c] = 1
print(bfs())dp로 풀기
import sys
n, k = map(int, sys.stdin.readline().split())
coin = [int(sys.stdin.readline()) for _ in range(n)]
dp = [1e9]*(k+1)
dp[0] = 0
coin.sort()
for c in coin:
for i in range(c, k+1):
dp[i] = min(dp[i-c]+1, dp[i])
print(dp[k]) if dp[k] != 1e9 else print(-1)