[백준] 부분수열의 합

https://www.acmicpc.net/problem/14225

14225번: 부분수열의 합

우선 문제부터 간단하게 요약하면,

 

수열 S가 주어질 때, 해당 수열의 부분수열의 합으로 나올 수 없는 가장 작은 자연수를 구해야 하는 문제입니다.

 

<Solution>

우선 문제에서 수열의 길이가 20이하로 주어졌기 때문에, dfs로 충분히 해결할 수 있음을 알 수 있습니다. 그리고 각각의 숫자들이 10만 보다 작거나 같다고 했으니, 

bool canMake[20*100000+10];

다음과 같은 구조를 만들어 dfs를 수의 갯수 깊이만큼 갔을 때, 만들 수 있는지 없는지를 저장하면서 문제를 해결 하면 됩니다. 

 

실제 구현은 아래와 같습니다. 

#include <iostream>

using namespace std;

int N;
int intArray[25];
bool canMake[20*100000+10];

void dfs(int curStep, int curVal){
    // when will it end?
    if(curStep == N){
        canMake[curVal] |= 1;
        return;
    }
    // o select
    dfs(curStep+1, curVal+intArray[curStep]);
    // x select
    dfs(curStep+1, curVal);
}

int main(){
    cin >> N;
    for(int i = 0; i<N; i++){
        cin >> intArray[i];
    }
    
    // fill canMake array
    dfs(0, 0);
    // get answer
    for(int i = 1; ;i++){
        if(!canMake[i]){
            cout << i << endl;
            break;
        }
    }

    return 0;
}