[백준] 14225번 부분수열의 합

문제 링크: https://www.acmicpc.net/problem/14225

문제

수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오.

예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 수 있다. 하지만, 4는 만들 수 없기 때문에 정답은 4이다.

입력

첫째 줄에 수열 S의 크기 N이 주어진다. (1 ≤ N ≤ 20)

둘째 줄에는 수열 S가 주어진다. S를 이루고있는 수는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 출력한다.

문제 이해

수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수.
총 경우의 수는 2^20까지 나올수 있다. 그래서 충분히 완전탐색으로 구현 가능.
나는 combination을 활용해서 구현했다.
최소 숫자를 확인하기 위해, 2,000,000의 boolean배열을 만들어서 확인하였다.
1. 입력
2. 조합 1~N까지의 조합을 백트랙킹으로 구현.
3. 위에서 조합이 완성될 때마다 더해서 해당 수에 true
4. 2-3번의 반복이 끝나면, boolean배열을 확인. for문을 최소로 하기위해 계산된 값중 maxNum까지만 돌린다.

코드 구현(c++)

#include <iostream>
#include <vector>

using namespace std;

bool check[20] = {false, };
int nums[20];
bool numCheck[2000000] = {false, };

int numSize;
int maxNum = -1;

void cal(){
    int temp = 0;
    for(int i = 0 ; i < numSize ; i++){
        if(check[i]) temp += nums[i];
    }
    numCheck[temp] = true;
    maxNum = max(maxNum, temp);
}

void combination(int n, int cnt, int maxCnt){
    if(cnt == maxCnt){
        cal();
    }
    else{
        for(int i = n ; i < numSize ; i++){
            if(!check[i]){
                check[i] = true;
                combination(i, cnt + 1, maxCnt);
                check[i] = false;
            }
        }
    }
}
int checkMinNum(){
    for(int i = 1 ; i <= maxNum ; i++){
        if(!numCheck[i]) return i;
    }
    return maxNum + 1;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

    cin >> numSize;
    for(int i = 0 ; i < numSize ; i++){
        cin >> nums[i];
    }
    for(int i = 1 ; i <= numSize ; i++){
        combination(0, 0, i);
    }

    cout << checkMinNum() << "\n";
    
}