백준
백준 소스코드 [C++] 14225 부분수열의 합
Hani_Levenshtein
2021. 4. 2. 09:47
14225번: 부분수열의 합
수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들
www.acmicpc.net
백준 소스코드 [C++] 14225 부분수열의 합
#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
#include <vector>
#include <math.h>
#include <stack>
#include <bitset>
#include <string>
#include <set>
#include <map>
#include <unordered_map>
#include <sstream>
#include <cstdlib>
#define all(v) v.begin(), v.end()
#define pii pair<int, int>
#define pli pair<ll, int>
#define make_unique(v) sort(all(v)), v.erase(unique(all(v)), v.end())
typedef long long ll;
using namespace std;
int n;
vector<int> v;
bool chk[2000001];
void memo(int start, int sum) {
if (start == n) {
chk[sum] = true;
return;
}
memo(start + 1, sum);
memo(start + 1, sum + v[start]);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
v.resize(n);
for (int i = 0;i < n;i++) cin >> v[i];
memo(0, 0);
for (int i = 1;i < 2000001;i++) {
if (chk[i] == false) {
cout << i;
break;
}
}
return 0;
}