13137번: Exchange Problem

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


$O(np)$

unbounded knapsack problem 솔루션을 변형한다.

#include<cstdio>
int n, dp[100001];
int main() {
    scanf("%d", &n);
    for (int i = 0, x; i < n; i++) {
        scanf("%d", &x);
        for (int j = x; j <= 1e5; j++) if (dp[j] && dp[j] <= dp[j - x]) {
            puts("No");
            return 0;
        }
        else dp[j] = dp[j - x] + 1;
    }
    puts("Yes");
    return 0;
}