[ boj : 14225 ]부분수열의 합

www.acmicpc.net/problem/14225

14225번: 부분수열의 합

문제 : 주어진 수들을 조합해서 만들 수 없는 수들중 가장 작은 수를 구해라

 

해설 : n이 최대 20이니 모든 경우의 수를 해보면 되겠죠. 그리고 만들 수 없는 수를 구하기 위해선 만들 수 있는 수를 체크해 두고 1부터 200만 까지 증가시켜가며 만들 수 없는 수들 중 가장 작은수를 구하면 됩니다.

만들 수 있는 수들을 set에다가 저장해 두면 O(logn) 만에 구할 수 있습니다.

#include<bits/stdc++.h>

using namespace std;

int n;
int arr[20],visit[20];
set<int> s;

void dfs(int depth);

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)cin >> arr[i];
	dfs(0);
	for (int i = 1; i <= 2000000; i++)
		if (s.find(i) == s.end())
			return cout << i, 0;
}
void dfs(int depth)
{
	if (depth == n) {
		int sum = 0;
		for (int i = 0; i < n; i++)
			if (visit[i])
				sum += arr[i];
		s.insert(sum);
		return;
	}

	visit[depth] = 1;
	dfs(depth + 1);

	visit[depth] = 0;
	dfs(depth + 1);
}