Link
https://www.acmicpc.net/problem/2624
Detail
dp로 테이블을 작성해나가는 동전유형의 기출중 한 문제다.
2차원 테이블을 만드는데, 이때 두 기준은
- i : 0번째 동전부터 i번째 동전까지 사용했을 때
- j : j원을 채울 수 있는 경우의 수 라고 지정하는 것이 기본이다.
이때. j를 0부터가 아니라 target부터 거꾸로 들어가며 채워간다면, dp를 이차원 테이블이 아닌 1차원 배열로도 해결이 가능하다.
배낭문제에서 1차원배열로 해결이 가능함을 며칠전에 알고 적용해보았다.
시간복잡도 자체는 10000 * 10000 * 100 이라 아슬아슬 할 수도 있다고 생각했는데, 통과하는데에는 문제가 없었다.
Code
#include<bits/stdc++.h>
using namespace std;
int main() {
int target, coin_cnt;
cin >> target >> coin_cnt;
// <value, cnt>
vector<pair<int, int>> coins(coin_cnt);
for(int i = 0; i < coin_cnt; i++) {
cin >> coins[i].first;
cin >> coins[i].second;
}
vector<int> dp(target + 1, 0);
dp[0] = 1;
// 3중 for
// k * T * n
// 10000 * 10000 * 100
for(pair<int, int>& coin : coins) {
for(int money = target; money >= 0; money--) {
for(int cnt = 1; cnt <= coin.second; cnt++) {
int before = money - coin.first * cnt;
if(before < 0) break;
dp[money] += dp[before];
}
}
}
cout << dp[target] << '\n';
}