Coin Combinations I
문제
https://cses.fi/problemset/task/1635/
문제 요약
주어진 동전들을 통해 목표합을 만드는 경우의 수를 구한다.
- 동전의 중복 사용을 허용
- 중요! 동전 순서가 다르면, 다른 경우로 인정
CODE
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mxN=100, mxX=1e6, mod=1e9+7;
int n, x, c[mxN+1];
int dp[mxX+1];
int main() {
cin >> n>> x;
for(int i=0;i<n; i++) {
cin >> c[i];
}
dp[0]=1;
for(int i=1; i<=x; i++) {
for(int j=0; j<n; j++) {
if(i>=c[j]) {
dp[i] = (dp[i] + dp[i-c[j]])%mod;
}
}
}
cout << dp[x];
}
점화식
if(i>=c[j]) {
dp[i] = (dp[i] + dp[i-c[j]])%mod;
}
놓치기 쉬운 부분
1. dp[0]=1 코드 누락
728x90
반응형
'알고리즘' 카테고리의 다른 글
[BOJ/백준] 11053번 - 가장 긴 증가하는 부분 수열 (0) | 2021.07.21 |
---|---|
[BOJ/백준] 2293번 - 동전 1 (0) | 2021.07.21 |
[CSES] Minimizing Coins (0) | 2021.07.21 |
[C++] 그래프 표현 (0) | 2021.07.19 |
[BOJ/백준] 1904번 - 01타일 (0) | 2021.07.11 |