[SWEA] 2817 부분 수열의 합

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

풀이

DFS로 모든 경우를 확인해보면 해결할 수 있다. 이 때 숫자들의 합이 k를 넘는 경우를 가지치기하여 최적화하였다.

코드

#include <iostream>
#include <vector>
using namespace std;

int ans, n, k;
vector<int> v;

void dfs(int idx, int cnt, int sum) {
    if (sum > k) return;
    if (sum == k) {
        ans++;
        return;
    }

    for (int i = idx + 1; i < n; i++)
        dfs(i, cnt + 1, sum + v[i]);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    for (int c = 1; c <= t; c++) {
        ans = 0;
        cin >> n >> k;
        v = vector<int>(n);
        for (int i = 0; i < n; i++)
            cin >> v[i];
        dfs(-1, 0, 0);
        cout << '#' << c << ' ' << ans << '\n';
    }
}