2624번: 동전 바꿔주기

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


$O(tk)$

dp[i][j]: p[1...i]를 이용하여 j원을 만드는 경우의 수
dp[i][j]=dp[i-1][j]+dp[i-1][j-pi]+dp[i-1][j-pi*2]+...+dp[i-1][j-pi*ni]
dp[i][j-pi]=dp[i-1][j-pi]+dp[i-1][j-pi*2]+...+dp[i-1][j-pi*(ni+1)]
빼서 정리하면
dp[i][j]=dp[i-1][j]+dp[i][j-pi]-dp[i-1][j-pi*(ni+1)]

#include<cstdio>
int t, k, dp[101][10001] = { 1 }, p, n;
int main() {
    scanf("%d%d", &t, &k);
    for (int i = 1; i <= k; i++) {
        scanf("%d%d", &p, &n);
        for (int j = 0; j <= t; j++)
            dp[i][j] = dp[i - 1][j] + (j / p ? dp[i][j - p] : 0) - (j / p > n ? dp[i - 1][j - p*n - p] : 0);
    }
    printf("%d", dp[k][t]);
    return 0;
}