[백준 14225] 부분수열의 합 (C++)

문제 링크: https://www.acmicpc.net/problem/14225

14225번: 부분수열의 합

1. 주의할 점

- 부분수열의 합으로 만들어 지는 수에 대해 중복 처리가 필요하다(따로 값을 저장할 시)

 

2. 구현

- Set을 이용해 부분수열의 합을 저장한다

- Cal() 함수의 경우 부분수열로 만들 수 있는 모든 수를 Set에 저장한다

- Set의 N번째와 N+1번째에 저장된 수의 차이가 1을 넘으면 N번째 수 +1을 출력한다

- Set의 Iterator를 통해 Set의 첫 번째 수가 1이 아니면 1을 출력하도록 한다

- Set에 저장된 모든 수가 1의 차이를 가지면, Set에 저장된 최댓값 +1을 출력한다

 

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
int num, arr[20];
set<int> s;

void cal(int idx, int sum) {
	if(idx == num) return;
	sum += arr[idx];
	if (s.find(sum) == s.end())		s.insert(sum);
	cal(idx + 1, sum);		//포함 하는 경우
	cal(idx + 1, sum-arr[idx]);		//포함 안하는 경우
}

int main() {
	cin >> num;
	for (int i = 0; i < num; i++) {
		cin >> arr[i];
		s.insert(arr[i]);
	}
	cal(0, 0);
	set<int> ::iterator it1 = s.begin(), it2;
	if (*it1 != 1) cout << 1;
	else {
		bool avail = false;
		while (1) {
			it2 = ++it1;
			if (it2 == s.end()) break;
			--it1;
			int a = *it2;
			int b = *it1;
			if (a - b != 1) {
				cout << b + 1;
				avail = true;
				break;
			}
			else
				it1 = it2;
		}
		if (!avail) {
			it2 = s.end();
			--it2;
			int result = *it2;
			cout << result + 1;
		}
	}
	system("pause");
	return 0;
}