전형적인 DP 문제이다.
이차원 배열 dp를 만들고 dp[i][j]에는 i번째 동전까지 사용했을 때, j원을 만들 수 있는 가능한 경우의 수를
저장하는 방식으로 해결했다.
C++
더보기
#include <iostream>
#include <vector>
using namespace std;
int cnt, k;
int main(void)
{
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int t;
cin >> t >> k;
vector<pair<int, int>> vec(k + 1);
vector<vector<int>> dp(k + 1, vector<int>(t + 1));
for (int i = 1; i <= k; ++i)
cin >> vec[i].first >> vec[i].second;
dp[0][0] = 1;
for (int i = 1; i <= k; ++i) {
for (int j = 0; j <= t; ++j) {
for (int k = 0; k <= vec[i].second; ++k) {
if (j - k * vec[i].first >= 0)
dp[i][j] += dp[i - 1][j - k * vec[i].first];
else
break;
}
}
}
cout << dp[k][t];
return 0;
}
728x90
'Problem Solving > BaekJoon' 카테고리의 다른 글
2056 작업 (0) | 2021.02.06 |
---|---|
1987 알파벳 (0) | 2021.02.02 |
1806 부분합 (0) | 2021.02.02 |
2228 구간 나누기 (0) | 2021.01.15 |
4386 별자리 만들기 (0) | 2021.01.15 |