[BOJ 2294] 동전 2
- 문제풀이
문제
n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.
입력
첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.
출력
첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 1sec (추가 시간 없음) | 128MB |
풀이
$n$가지 종류의 동전을 사용하여 그 가치의 합이 정확히 $k$원이 되도록 할 때, 필요한 동전의 최소 개수를 구하는 문제다. 각 동전은 개수 제한 없이 사용할 수 있으며, 가치가 같은 동전이 여러 번 주어질 수 있다는 점에 유의해야 한다.
목표 금액 $k$원을 만들기 위한 최소 동전 개수는, 이전에 계산된 더 작은 금액의 최적해를 활용하여 구할 수 있다. 따라서 이 문제는 다이나믹 프로그래밍을 통해 효율적으로 해결할 수 있다.
먼저 $DP[i]$를 “가치의 합이 $i$원이 될 때 사용한 동전의 최소 개수”라고 정의하자. 가치가 $a$인 동전 하나를 추가하여 $i$원을 만드는 경우, 이전 상태인 $DP[i-a]$원에 동전 한 개를 더한 값이 된다. 이를 활용한 점화식은 다음과 같다.
\[DP[i] = \min(DP[i], DP[i - a] + 1)\]초기 상태에서 $DP[0]$은 $0$으로 설정하고, 나머지 모든 칸은 문제에서 나올 수 없는 큰 값(INF)으로 초기화한다. 이후 입력으로 주어지는 각 동전의 가치 $a$에 대해, $a$원부터 $k$원까지 차례대로 확인하며 dp 테이블을 업데이트한다.
목표 금액인 $k$의 범위는 $1 \leq k \leq 10\,000$이며, 동전의 종류는 $1 \leq n \leq 100$이다. 따라서 전체 시간 복잡도는 $O(nk)$가 되며, 이는 약 $1\,000\,000$번의 연산으로 제한 시간 1초 내에 충분히 통과 가능하다. 만약 모든 연산이 끝난 후 $DP[k]$가 여전히 INF라면 해당 금액을 만드는 것이 불가능하므로 $-1$을 출력한다.
소스코드
Github Link : Source Code
참고 알고리즘 : 다이나믹 프로그래밍