2817 부분수열의 합

SWEA::2817 부분수열의 합

모든 부분수열에 대해 합을 구하는 문제이다.

첫번째 방법으로

나는 누적되며 나올 수 있는 모든 합 중에 k를 초과하지 않는 것에 대해서

vector 에 누적시키면서 카운팅 했다.

#include <stdio.h>
#include <vector>
using namespace std;
 
int t, n, k, res;
 
int main() {
 
    scanf("%d", &t);
    for (int tc = 1; tc <= t; tc++) {
        int a[20];
        vector<int> all;//k를 초과하지 않는 경우들을 누적시킬 벡터
        int cnt = 0;
 
        scanf("%d %d", &n, &k);
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
            if (a[i] == k) {
                cnt++;
            }
        }
 
        for (int i = 0; i < n; i++) {
            all.push_back(a[i]);
            int size = all.size();
            //누적된 벡터내의 원소들과 더해 k가 되는지 확인
            //k==sum 이면 cnt++;
            //k<sum 이면 더해봤자 어차피 k보다 크므로 continue;
            //k>sum 이면 vector에 sum원소 추가
            for (int j = 0; j < size - 1; j++) {
                int sum = a[i] + all.at(j);
                if (sum == k) {
                    cnt++;
                }
                else if (sum > k) {
                    continue;
                }
                else {
                    all.push_back(sum);
                }
            }
        }
        printf("#%d %d\n", tc, cnt);
    }
}

두번째 방법은 백트래킹으로 결과를 찾았다.

#include <stdio.h>
using namespace std;
 
int t, n, k , total, cnt;
int a[20];
 
 
//백트래킹
void dfs(int v,int total) {
    total += a[v];
 
    if (total == k) {
        cnt++;
    }
    else if (total > k) {
 
    }
    else {
        for (int i = v + 1; i < n; i++) {
            dfs(i, total);
        }
    }
 
    total -= a[v];
}
int main() {
 
    scanf("%d", &t);
    for (int tc = 1; tc <= t; tc++) {
 
        cnt = 0;
 
        scanf("%d %d", &n, &k);
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
        }
 
        for (int i = 0; i < n; i++) {
            total = 0;
            dfs(i,0);
        }
 
        printf("#%d %d\n", tc, cnt);
    }
 
}