백준, BOJ, 14225번, 부분수열의 합 C++ [CPP] ★★

 

어렵진 않지만 실수할 경우가 많은 문제가 아닌가 싶다.

 

 

 

https://www.acmicpc.net/submit/14225/44550103

 

---

 

#맞은 풀이

#include <bits/stdc++.h>

using namespace std;

int N;
vector<int> vec;
unordered_map <int,int> dict; //그냥 숫자체크

void func(int cnt, int result){
    
    if(cnt == N){
        //cout << result << '\n';
        dict[result] = 1;
        return;
    }
    
    
        //더하는 경우, 그대로인 경우 2가지
        func(cnt + 1, result + vec[cnt]);
        func(cnt + 1, result);
        
    
}


int main(){
    cin >> N;
    for(int i = 0; i<N; i++){
        int x;
        cin >> x;
        vec.push_back(x);
    }
    
    func(0,0);
    long long num = 1;
    
    while(true){
        if(dict[num] == 0){
            cout << num << '\n';
            break;
        }
        else{
            num++;
        }
    }


    return 0;
}

 

여기서 중요한점은 백트래킹을 어떻게 하느냐인데

cnt는 선택의 경우의 수다.

한 번의 선택마다 2가지 경우가 있다.

일반적으로는 선택을 하면 복원을 하는데 여기서는 복원할 필요가 없다.

2가지만 있어서 그렇다.

복원을 하는 이유는 N가지 선택을 할 수 있어서 인데

여기서는 2가지 밖에 없다.