3752. 가능한 시험 점수

동전 문제와 동일하다.

맨 처음은 문제가 없으므로 0점만 가능하다. (a[0] = 1)

그 다음에는 배점을 입력받으면서 가능한 경우의 수를 배열에 기록한다.

#include <iostream>
using namespace std;
 
int t, n;
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> t;
    for (int tc = 1; tc <= t; ++tc) {
        int a[10101] = { 0, };
        cin >> n;
        int r = 0, temp = 0, ans = 0;
        a[0] = 1;
        while (n--) {
            cin >> temp;
            r += temp;
            for (int i = r; i >= temp; --i) 
                a[i] |= a[i - temp];
        }
        for (int i = 0; i <= r; ++i) 
            ans += a[i];
        cout << "#" << tc << " " << ans << '\n';
    }
    return 0;
}