[CSES] Coin Combinations I

Coin Combinations I

문제

https://cses.fi/problemset/task/1635/

CSES - Coin Combinations I

 

문제 요약

주어진 동전들을 통해 목표합을 만드는 경우의 수를 구한다.

• 동전의 중복 사용을 허용
• 중요! 동전 순서가 다르면, 다른 경우로 인정

 

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 코드 누락