[C++] 백준 BOJ 2293 동전1

문제 링크 : https://boj.kr/2293

// BOJ 2293 동전1
#include <bits/stdc++.h>
 
using namespace std;
 
int dp[10001];
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("../input.txt", "r", stdin);
 
    int num, result;
    cin >> num >> result;
 
    vector<int> coin(num + 1);
    vector<int> dp(result + 1, 0);
    for (int i = 1; i <= num; i++)
        cin >> coin[i];
 
    dp[0] = 1;
 
    for (int cn : coin)
        for (int i = 1; i <= result; i++)
            if (i - cn >= 0)
                dp[i] += dp[i - cn];
 
    cout << dp[result];
 
    return 0;
}