백준_14225_부분수열의 합

🎈문제: https://www.acmicpc.net/problem/14225

14225번: 부분수열의 합

 

🎈알고리즘: 브루트포스 - 비트마스크

 

🎈부분수열 개념) 부분 수열은 원래 수열의 순서를 바꿀 수 없다.

예를 들어, 수열 S={1,2,5}의 부분수열은 {},{1},{2},{5},{1,2},{1,5},{2,5},{1,2,5} 이다. ({5,2} 등은 부분수열이 아니다!)

 

🎈부분수열을 만드는 방법)

1. 재귀 호출

2. 비트마스크 (👉이번에는 비트마스크로 풀어보았다.)

 

🎈아이디어: 해당 숫자가 부분수열의 합으로 나온적이 있으면 check 배열에 true를 저장

 

🎈코드:

#include <iostream>
#include <vector>
#define MAX (20*100000+1)
using namespace std;

bool check[MAX];

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int N;
	cin >> N;
	vector<int> s(N);
	for (int i = 0; i < N; i++) {
		cin >> s[i];
	}
	for (int i = 0; i < (1 << N); i++) {
		int sum = 0;
		for (int j = 0; j < N; j++) {
			if ((i & (1 << j)) != 0) {
				sum += s[N - 1 - j];
			}
		}
		check[sum] = true;
	}
	for (int i = 1;; i++) {
		if (check[i] == false) {
			cout << i << '\n';
			break;
		}
	}
	return 0;
}