2293번: 동전 1

https://www.acmicpc.net/problem/2293

$O(nk)$

Unbounded Knapsack Problem 이다.

#include<stdio.h>
int dp[10001], n, k;
int main() {
    dp[0] = 1;
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++) {
        int a;
        scanf("%d", &a);
        for (int j = a; j <= k; j++) dp[j] += dp[j - a];
    }
    printf("%d", dp[k]);
    return 0;
}