[20/07/05] E. 부분수열의 합 (14225)

이 문제를 처음 봤을 때 어떻게 풀어야 할지 몰랐었다. n이 작아서 완전탐색이 가능하다고 생각이 들었지만 n 개수에 따라서 반복문을 만들어야 할 것 같아서 패스했다. 다음으로 규칙이 있나 생각이 들어서 계속 고민해봤지만 답을 구하지 못했다. 알고보니 이 문제는 비트마스크를 사용해서 부분집합을 구할 수 있었다. 비트마스크는 원소 하나를 하나의 비트로 표현하는 걸 말한다. 비트마스크와 비트연산으로 완전탐색을 어떻게 하는지 공부해봤다.

 

 

비트에 대한 기본 개념을 공부했다.

 

 

위의 완전탐색을 이용해서 부분수열의 합을 구한 다음 해당 값을 1로 설정해둔다. 완전 탐색이 끝나면 ans배열을 1부터 1이 아닌 값을 찾아서 출력한다. 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define xx first
#define yy second
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

int main() {
    int n;
    scanf("%d", &n);

    vector<int> s(n);
    for (int i = 0; i < n; i++)
        scanf("%d", &s[i]);
    
    vector<int> count(2000005, 0);
    for (int i = 0; i < (1 << n); ++i) 
    { 
        int sum = 0;
        for (int j = 0; j < n; ++j)
        { 
            if (i & (1 << j)) 
                sum += s[j];
        }
        count[sum] = 1;
    }
    
    for (int i = 1; i <= 2000000; i++)
    {
        if (count[i] != 1)
        {
            printf("%d\n", i);
            break ;
        }
    }
    
    return 0;
}

새로운 개념이라서 재밌었음. 하지만 비트 연산 어렵다..