이번에는 백준 2293번 동전 1 문제를 풀어보았습니다.
각 동전은 몇 개라도 사용할 수 있고, 동전의 순서만 다른 경우는 같은 경우로 봅니다.
따라서 dp[x]를 현재까지 확인한 동전들로 x원을 만드는 경우의 수로 두고, 동전 종류를 하나씩 바깥쪽 반복문에서 고정하면서 금액을 증가시키는 방식으로 해결하였습니다.
문제 설명
N가지 종류의 동전이 주어지고, 각 동전은 원하는 만큼 사용할 수 있습니다.
이 동전들을 사용해서 정확히 K원을 만드는 경우의 수를 구해야 합니다.
단,
1 + 2 + 2
2 + 1 + 2
2 + 2 + 1처럼 사용한 동전의 구성은 같고 순서만 다른 경우는 모두 같은 경우로 봅니다.
따라서 단순히 모든 순서를 세는 것이 아니라, 동전 조합의 개수를 구해야 합니다.
풀이 아이디어
dp[amount]를 다음과 같이 정의하였습니다.
dp[amount]
=
현재까지 확인한 동전들을 이용해서
amount원을 만드는 경우의 수초기 상태는
dp[0] = 1;입니다.
0원을 만드는 방법은 아무 동전도 사용하지 않는 한 가지 방법이 있기 때문입니다.
이후 동전을 하나씩 확인하면서
for (int curr_coin : coin)현재 동전을 사용할 수 있는 모든 금액에 대해
dp[amount] += dp[amount - curr_coin];를 수행합니다.
amount - curr_coin원을 만드는 기존 방법에 현재 동전 하나를 추가하면 amount원을 만들 수 있기 때문입니다.
코드
#include <bits/stdc++.h>
using namespace std;
vector<int> dp;
vector<int> coin;
int N,K;
int main() {
ios_base::sync_with_stdio(false);
cout.tie(nullptr);
cin >> N >> K;
dp.resize(K+1,0);
dp[0] = 1;
coin.resize(N);
for (int i=0; i<N; i++) {
cin >> coin[i];
}
for (int curr_coin : coin) {
for (int amount = curr_coin; amount <= K; amount++) {
dp[amount] += dp[amount - curr_coin];
}
}
cout << dp[K];
return 0;
}풀이 흐름
-
동전의 종류
N과 목표 금액K를 입력받습니다. -
dp배열을0으로 초기화합니다. -
dp[0] = 1로 설정합니다. -
사용할 수 있는 동전들을 입력받습니다.
-
동전을 하나씩 순회합니다.
-
현재 동전
curr_coin부터K까지 금액을 증가시키며 확인합니다. -
dp[amount - curr_coin]을dp[amount]에 더합니다. -
모든 동전을 처리한 뒤
dp[K]를 출력합니다.
구현 포인트
1. dp의 의미
vector<int> dp;dp[amount]는 현재까지 확인한 동전들을 이용하여 amount원을 만드는 경우의 수입니다.
예를 들어 현재까지 1원, 2원 동전을 확인했다고 했을 때
dp[4]에는 1원과 2원만 이용해서 4원을 만드는 경우의 수가 저장됩니다.
2. dp[0] = 1인 이유
dp[0] = 1;0원을 만드는 방법은
아무 동전도 사용하지 않는 방법한 가지가 있습니다.
이 값이 이후 DP 갱신의 시작점이 됩니다.
예를 들어 현재 동전이 3원이라면
dp[3] += dp[0];이 됩니다.
dp[0] = 1이기 때문에
3원 동전 하나만 사용하는 경우가 정상적으로 dp[3]에 추가됩니다.
3. 동전을 바깥쪽 반복문에 두는 이유
for (int curr_coin : coin) {이 문제의 가장 중요한 부분입니다.
동전 종류를 바깥쪽 반복문으로 두면 현재 동전을 기준으로 조합을 만들어가게 됩니다.
예를 들어 동전이
1, 2라고 하면 먼저 1원짜리 동전만 사용하는 경우들을 계산하고, 그다음 2원짜리 동전을 추가하는 경우들을 계산합니다.
이렇게 하면
1 + 2
2 + 1을 서로 다른 경우로 세지 않습니다.
즉, 순서가 아니라 조합만 세기 위해 동전 반복문을 바깥에 둡니다.
4. amount를 증가시키는 이유
for (int amount = curr_coin; amount <= K; amount++) {현재 동전은 몇 개라도 사용할 수 있습니다.
따라서 금액을 작은 값부터 큰 값으로 증가시키면서 DP를 갱신합니다.
예를 들어 현재 동전이 2라면
dp[2]
dp[4]
dp[6]
...을 계산하는 과정에서 이미 이번 반복에서 갱신된 값을 다시 사용할 수 있습니다.
이 때문에 2원짜리 동전을
1개
2개
3개
...여러 번 사용하는 경우까지 자연스럽게 포함됩니다.
5. 점화식
dp[amount] += dp[amount - curr_coin];현재 amount원을 만드는 경우를 생각해보겠습니다.
마지막에 현재 동전 curr_coin을 하나 사용한다고 하면 그 이전에는
amount - curr_coin원을 만들어 놓아야 합니다.
따라서
amount - curr_coin원을 만드는 모든 경우
+
현재 동전 하나를 이용하면 amount원을 만드는 새로운 경우들을 만들 수 있습니다.
그래서
dp[amount]
=
dp[amount]
+
dp[amount - curr_coin]로 갱신합니다.
6. 예시로 보는 동작
동전이
1, 2이고 목표 금액이 4라고 하겠습니다.
처음에는
dp[0] = 1
dp[1] = 0
dp[2] = 0
dp[3] = 0
dp[4] = 0입니다.
먼저 1원 동전을 처리합니다.
dp[1] += dp[0] → 1
dp[2] += dp[1] → 1
dp[3] += dp[2] → 1
dp[4] += dp[3] → 1따라서
1+1+1+1한 가지 방법이 만들어집니다.
이제 2원 동전을 처리합니다.
dp[2] += dp[0]
dp[3] += dp[1]
dp[4] += dp[2]최종적으로 4원을 만드는 방법은
1 + 1 + 1 + 1
1 + 1 + 2
2 + 2총 3가지가 됩니다.
7. 순서가 다른 경우를 중복으로 세지 않는 이유
이 문제에서는
1 + 2
2 + 1을 같은 경우로 봅니다.
코드에서는 동전을 하나씩 순서대로 확장합니다.
for (int curr_coin : coin)예를 들어 1원 동전을 먼저 처리한 뒤 2원 동전을 처리하면 2원 동전을 추가하는 시점에는 이미 1원 동전들로 만들어진 경우에 2원을 추가하게 됩니다.
반대로 다시 1원을 뒤에 붙여
2 + 1이라는 새로운 순서를 만드는 과정은 발생하지 않습니다.
따라서 순열이 아니라 조합만 계산됩니다.
8. 같은 동전을 여러 번 사용할 수 있는 이유
금액 반복문을
for (int amount = curr_coin; amount <= K; amount++)처럼 증가하는 방향으로 진행합니다.
현재 반복에서 갱신된 dp 값을 다시 뒤에서 사용할 수 있기 때문에 동일한 동전을 여러 번 사용하는 것이 가능합니다.
예를 들어 동전이 3원이라면
dp[3] += dp[0]
dp[6] += dp[3]
dp[9] += dp[6]처럼 이어질 수 있습니다.
즉,
3
3 + 3
3 + 3 + 3과 같은 경우들이 자연스럽게 만들어집니다.
9. 1차원 DP만으로 해결 가능한 이유
처음에는
dp[동전 종류][금액]형태의 2차원 DP를 생각할 수도 있습니다.
하지만 현재 동전을 하나씩 순서대로 처리하면서 dp[amount]를 갱신하면 이전 동전들에 대한 정보가 그대로 유지됩니다.
따라서 동전 종류 차원을 따로 저장할 필요 없이
dp[금액]하나만으로도 해결할 수 있습니다.
이를 통해 공간을 줄일 수 있습니다.
10. 전체 로직 정리
전체 흐름은 다음과 같습니다.
dp[0] = 1
↓
동전 하나 선택
↓
현재 동전 가치부터 K까지 순회
↓
dp[amount] += dp[amount - coin]
↓
다음 동전 처리
↓
dp[K] 출력핵심은
동전 종류를 바깥쪽 반복문
금액을 안쪽 반복문으로 두는 것입니다.
이 구조 덕분에 동전의 사용 순서는 무시하고 조합의 개수만 계산할 수 있습니다.
시간복잡도
동전의 종류는 N개이고, 각 동전마다 최대 K개의 금액을 확인합니다.
따라서 시간복잡도는
O(N × K)입니다.
N ≤ 100, K ≤ 10,000이므로 최대 약 100만 번 정도의 연산으로 해결할 수 있습니다.
dp 배열은 K + 1개의 값을 저장하고, coin 배열에는 N개의 값을 저장하므로 공간복잡도는
O(K + N)이며 DP 기준으로 보면
O(K)입니다.
