[백준 14225] 부분수열의 합

[백준 14225] 부분수열의 합

문제 링크

#include "header.h"
using namespace std;
#define MAX 2000005
int N;
vector <int> numbers;
int visit[24];
int can[MAX];
void input(){
    cin >> N;
    for(int i=0; i<N; i++){
        int n;
        cin >> n;
        numbers.push_back(n);
    }
}

void dfs(int now, int idx){
    
    can[now] = 1;

    for(int i=idx; i<numbers.size(); i++){
        if(!visit[i]){
            visit[i] = 1;
            dfs(now + numbers[i], i+1);
            visit[i] = 0;
        }
    }

}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    input();
    dfs(0, 0);

    for(int i=0; i<MAX; i++){
        if(!can[i]){
            cout << i << endl;
            break;
        }
    }


    return 0;
}

• dfs로 만들 수 있는 부분수열을 모두 구한다.
• can 배열에 구한 부분수열을 체크 해 준다.
• dfs 종료 이후, can이 0인 제일 작은 숫자를 구한다.
• 범위를 조심해야 한다. 100000 * 20 으로 2백만으로 해 주었다.