이번에는 백준 2294번 동전 2 문제를 풀어보았습니다.
각 동전은 몇 개든 사용할 수 있고, 동전 가치의 합을 정확히 k원으로 만들면서 사용하는 동전의 개수를 최소화해야 합니다.
dp[x]를 x원을 만드는 데 필요한 최소 동전의 개수로 정의하고, 마지막으로 사용한 동전의 가치가 c라면 그 이전에는 x-c원을 만들어야 한다는 점을 이용하여 재귀 + 메모이제이션으로 해결하였습니다.
문제 설명
N가지 종류의 동전이 주어지고, 각각의 동전은 원하는 만큼 사용할 수 있습니다.
이 동전들을 이용해서 정확히 k원을 만들려고 합니다.
이때 사용한 동전의 개수를 최소화해야 하며, k원을 만들 수 없다면 -1을 출력해야 합니다.
예를 들어 사용할 수 있는 동전이
1, 5, 12이고 15원을 만들어야 한다면
5 + 5 + 5를 이용하여 3개의 동전으로 만들 수 있습니다.
풀이 아이디어
dp[x]를 다음과 같이 정의하였습니다.
dp[x] = x원을 만드는 데 필요한 최소 동전 개수현재 x원을 만든다고 생각했을 때, 마지막으로 사용한 동전의 가치가 coin이라면 그 동전을 사용하기 전에는
x - coin원을 만들어 놓아야 합니다.
따라서 현재 동전의 가치가 x보다 작거나 같다면
dp[x] = min(dp[x], dp[x - coin] + 1)로 생각할 수 있습니다.
모든 동전을 마지막 동전 후보로 확인하면서 가장 작은 값을 선택합니다.
이를 재귀 함수 solve(x)로 구현하고, 한 번 계산한 값은 dp[x]에 저장하여 같은 금액을 다시 계산하지 않도록 하였습니다.
코드
#include <bits/stdc++.h>
using namespace std;
int N,k;
int dp[100001];
vector<int> inp(100);
int solve(int n) {
if (dp[n] != -1) return dp[n];
int min_val = k+1;
for (int i = 0; i < N; i++) {
int coin_val = inp[i];
if (coin_val <= n) {
min_val = min(min_val, solve(n - coin_val) + 1);
}
}
return dp[n] = min_val;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N >> k;
for (int i=0; i<N; i++) {
cin >> inp[i];
}
fill(dp, dp + k + 1, -1);
dp[0] = 0;
int ret = solve(k);
cout << (ret > k ? -1 : ret) << '\n';
return 0;
}풀이 흐름
-
동전의 종류
N과 목표 금액k를 입력받습니다. -
사용할 수 있는 동전들의 가치를
inp에 저장합니다. -
dp배열을-1로 초기화합니다. -
dp[0] = 0으로 설정합니다. -
solve(k)를 호출하여k원을 만드는 최소 동전 개수를 구합니다. -
현재 금액
n에서 사용할 수 있는 모든 동전을 확인합니다. -
동전의 가치가
n보다 작거나 같다면 해당 동전을 마지막으로 사용하는 경우를 계산합니다. -
solve(n - coin) + 1중 가장 작은 값을 선택합니다. -
계산한 결과를
dp[n]에 저장합니다. -
최종 결과가
k보다 크다면 만들 수 없는 금액이므로-1을 출력합니다.
구현 포인트
1. DP의 의미
int dp[100001];dp[n]은
n원을 만들기 위해 필요한 최소 동전 개수를 의미합니다.
예를 들어
dp[10] = 2라면 주어진 동전들을 이용하여 10원을 만드는 데 최소 2개의 동전이 필요하다는 의미입니다.
2. 시작 상태
dp[0] = 0;0원을 만드는 데는 아무 동전도 필요하지 않습니다.
따라서
dp[0] = 0으로 설정합니다.
이 값이 재귀의 실질적인 종료 조건 역할도 합니다.
예를 들어 현재 금액과 동전 가치가 같다면
solve(coin - coin)
= solve(0)
= 0이 되고 여기에 현재 사용한 동전 하나를 더하여 1이 됩니다.
3. 현재 금액을 만드는 마지막 동전 생각하기
현재 n원을 만들어야 한다고 생각해보겠습니다.
마지막으로 사용한 동전의 가치가 coin_val이라면 그 동전을 사용하기 전에는
n - coin_val원을 만들어 놓아야 합니다.
따라서 현재 동전을 사용하는 경우 필요한 전체 동전 수는
solve(n - coin_val) + 1이 됩니다.
+1은 마지막에 사용하는 현재 동전 하나입니다.
4. 모든 동전을 마지막 후보로 확인
for (int i = 0; i < N; i++) {
int coin_val = inp[i];어떤 종류의 동전이 최적의 마지막 동전이 될지는 미리 알 수 없습니다.
따라서 모든 동전을 하나씩 확인합니다.
현재 동전의 가치가 만들려는 금액보다 큰 경우에는 사용할 수 없으므로
if (coin_val <= n)조건을 확인합니다.
5. 점화식
min_val = min(min_val, solve(n - coin_val) + 1);현재 동전을 마지막으로 사용한다고 했을 때 필요한 동전 개수와 지금까지의 최솟값을 비교합니다.
따라서 점화식은 다음과 같이 볼 수 있습니다.
dp[n]
=
min(dp[n - coin] + 1)단,
coin <= n인 모든 동전에 대해 비교합니다.
6. 같은 동전을 여러 번 사용할 수 있는 이유
문제에서는 하나의 동전을 몇 개든 사용할 수 있습니다.
예를 들어 3원짜리 동전을 이용하는 경우
solve(9)
→ solve(6)
→ solve(3)
→ solve(0)처럼 같은 종류의 동전을 여러 번 선택할 수 있습니다.
코드에서는 한 번 사용한 동전을 별도로 제거하거나 방문 처리하지 않으므로 자연스럽게 같은 동전을 계속 사용할 수 있습니다.
7. 메모이제이션
if (dp[n] != -1) return dp[n];같은 금액 n을 만드는 최소 동전 개수는 항상 동일합니다.
따라서 한 번 계산한 dp[n]은 다시 계산할 필요가 없습니다.
예를 들어 여러 경로를 통해 solve(20)이 호출되더라도 처음 한 번만 계산하고 이후에는 저장된 값을 바로 반환합니다.
이를 통해 재귀에서 발생하는 중복 계산을 줄일 수 있습니다.
8. 불가능한 상태 처리
int min_val = k+1;현재 금액을 만들 수 없는 경우를 표현하기 위해 초기값을 k+1로 설정하였습니다.
동전의 가치는 모두 자연수이므로 k원을 만들 수 있다면 필요한 동전의 최대 개수는 1원짜리 동전을 k개 사용하는 경우의 k개를 넘을 수 없습니다.
따라서
k보다 큰 값은 실제 정답이 될 수 없는 값으로 사용할 수 있습니다.
9. 만들 수 없는 금액에서도 DP 저장
return dp[n] = min_val;어떤 동전을 사용해도 n원을 만들 수 없다면 min_val에는 큰 값이 그대로 남게 됩니다.
이 값 역시 dp[n]에 저장합니다.
그러면 이후 같은 n원을 만들려고 할 때 다시 모든 동전을 확인하지 않고 바로 불가능한 상태라는 결과를 재사용할 수 있습니다.
10. 최종적으로 -1 출력
int ret = solve(k);
cout << (ret > k ? -1 : ret) << '\n';k원을 정상적으로 만들 수 있다면 최소 동전 개수는 k 이하입니다.
반대로 결과가 k보다 크다는 것은 실제 최소 동전 개수가 아니라 만들 수 없음을 표시하기 위해 사용한 큰 값이라는 의미입니다.
따라서
ret > k이면 -1을 출력합니다.
11. 중복된 동전 가치가 있어도 문제없는 이유
문제에서는 같은 가치의 동전이 여러 번 입력될 수도 있습니다.
예를 들어
1
5
5
10처럼 5원이 두 번 등장할 수 있습니다.
코드에서는 두 5원 동전을 각각 확인하게 되지만
min(min_val, solve(n - 5) + 1)이라는 같은 계산을 한 번 더 수행할 뿐 결과에는 영향을 주지 않습니다.
따라서 별도로 중복을 제거하지 않아도 정답을 구할 수 있습니다.
12. Top-Down DP 구조
이 코드는 목표 금액 k에서 시작하여 더 작은 금액으로 내려가는 방식입니다.
solve(k)
↓
solve(k - coin)
↓
solve(k - coin - coin)
↓
...
solve(0)즉, Top-Down DP + 메모이제이션 방식입니다.
필요한 상태를 재귀적으로 계산하고, 계산된 값은 dp에 저장하여 재사용합니다.
전체 로직 정리
전체적인 흐름은 다음과 같습니다.
solve(k)
↓
마지막으로 사용할 동전 하나 선택
↓
solve(k - coin) + 1
↓
모든 동전에 대해 확인
↓
가장 작은 값 선택
↓
dp[k]에 저장결국
현재 금액 n
=
이전 금액 n - coin을 만드는 최소 개수
+
현재 동전 하나라는 관계를 이용하여 문제를 해결하였습니다.
시간복잡도
계산해야 하는 DP 상태는
0 ~ k이므로 최대 k + 1개입니다.
각 상태마다 N개의 동전을 모두 확인하므로 시간복잡도는
O(N × K)입니다.
N ≤ 100, K ≤ 10,000이므로 최대 약 100만 번 정도의 연산으로 해결할 수 있습니다.
dp 배열에는 K개의 상태를 저장하고, 동전 배열에는 N개의 값을 저장하므로 공간복잡도는
O(K + N)이며, DP 기준으로 보면 O(K)입니다.
