[SWEA] 2817 부분수열의 합

2817 부분수열의 합

풀이)

3752 가능한 시험 문제 와 비슷하게 풀면 된다.

코드)

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
 
int arr[20];
int dp[100000];
 
int main() {
    //freopen("sample_input.txt", "r", stdin);
    int T = 0;
    scanf("%d", &T);
    for (int test_case = 1; test_case <= T; test_case++) {
        memset(dp, 0, sizeof(dp));
        memset(arr, 0, sizeof(arr));
        int n, k;
        scanf("%d %d", &n, &k);
        for (int i = 0; i < n; i++) {
            scanf("%d", &arr[i]);
        }
        dp[0] = 1;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += arr[i];
            for (int j = sum; j >= 0; j--) {
                if (dp[j]) {
                    dp[j + arr[i]] += dp[j];
                }
                
            }
        }
        printf("#%d %d", test_case, dp[k]);
        
    }
    return 0;
}