[백준/BOJ] 14225번 부분수열의 합 (C++)

www.acmicpc.net/problem/14225

14225번: 부분수열의 합

1182번 문제에서 조금 심화된 브루트 포스(완전 탐색) 문제입니다.

DFS를 이용해 만들어 낼 수 있는 부분수열의 합을 모두 구하고 이를 배열에 체크합니다. 모든 탐색이 끝난 후, 체크 배열에서 false인 첫 인덱스를 출력하고 종료합니다. 이때, 배열 범위안에 false인 인덱스가 없다면, 가장 큰 인덱스에서 +1을 한 값을 출력하면 됩니다.

 

#include <iostream>
using namespace std;

int n;
int s[21];
bool check[2000001];

void DFS(int idx, int sum) {
    if(idx == n) {
        check[sum] = true;
        return;
    }
    
    DFS(idx + 1, sum + s[idx]);
    DFS(idx + 1, sum);
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int maxx = 0;
    cin>>n;
    for(int i = 0; i < n; i++) {
        cin >> s[i];
        maxx += s[i];
    }
    
    DFS(0, 0);
    
    bool flag = false;
    for(int i = 1; i <= maxx; i++) {
        if(!check[i]) {
            cout<<i;
            flag = true;
            break;
        }
    }
    if(!flag) cout << maxx + 1;
}