수열 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의 하위 시퀀스의 합이 될 수 없는 가장 작은 자연수를 인쇄합니다.
n번째 숫자가 추가되거나 추가되지 않으면 방문한 숫자가 각각 클리핑되어 표시됩니다.
이후 1번부터 체크하여 처음 방문하지 않은 번호 방문시 출력하고 종료합니다.
#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL)
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int N, M, n(21), v(21), m(2000001), temp;
void dfs(int k,int sum) {
if (k >= N)return;
m(sum+n(k)) = 1;
dfs(k + 1, sum);
dfs(k + 1, sum + n(k));
}
int main() {
FAST;
int k = 0;
cin >> N;
rep(i, N) {
cin >> n(i);
}
dfs(0,0);
REP(i, 2000001) {
if (!m(i)) {
cout << i;
return 0;
}
}
}