BOJ 14225 : 부분수열의 합

문제 재정의

수열S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 출력해라

 

입력

수열S의 크기(1~20), 수열S{...}

 

출력

가장 작은 자연수 k

 

풀이

1) 재귀함수를 이용해 가능한 모든 부분수열의 합을 저장 (vector<int> allSum)

2) sort,unique함수로 allSum을 정렬하고 중복 요소 제거

3) allSum이 연속된 값을 가지지 않을 때 요소가 답이므로 출력

4) 만약 합의 첫번째 요소가 1이 아니면 무조건 1이 답이다.. 가장 작은 자연수는 1이니께

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N;
int num[20];
vector<int> allSum;

void go(int idx, int sum) {
	if (idx == N) {
		allSum.push_back(sum);
		return;
	}
	go(idx + 1, sum + num[idx]);
	go(idx + 1, sum);
}

int main() {

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> num[i];
	}

	go(0, 0);

	sort(allSum.begin(), allSum.end());
	unique(allSum.begin(), allSum.end());
	int answer = 0;

	//cout << "front:" << allSum[1] << "\n";
	//cout << "back:" << allSum.back() << "\n";

	
	int n = allSum.size();
	for (int i = 1; i < n; i++) {
		if (allSum[i] - allSum[i - 1] > 1) {
			answer = allSum[i-1] + 1;
			break;
		}
	}
	if (answer == 0) {
		if (allSum[1] != 1) {
			answer = 1;
		}
		else {
			answer = allSum.back() + 1;
		}
	}

	cout << answer;
	  
	return 0;
}