[BOJ]14225번: 부분수열의 합 (c++)

https://www.acmicpc.net/problem/14225

14225번: 부분수열의 합

 

방법 1: 백트랙킹

#include <iostream>
#include <vector>

using namespace std;

const int MAX = 100000 * 20;

void dfs(vector<int>& nums, vector<bool> &visit, int num, int idx)
{
	// 부분수열의 합계 num 방문체크 하기
	visit[num] = true;
	
	// 인덱스 범위를 넘으면 종료
	if (idx == nums.size())
	{
		return;
	}
	
	// idx번째 수를 포함하지 않는 경우
	dfs(nums, visit, num, idx + 1);

	// idx번째 수를 포함하는 경우
	dfs(nums, visit, num + nums[idx], idx + 1);
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	// 입력
	int N;
	cin >> N;
	vector<int> nums(N);
	for (int i = 0; i < N; ++i)
	{
		cin >> nums[i];
	}

	// 백트랙킹으로 가능한 부분집합의 합 모두 구하기
	vector<bool> visit(MAX + 1);
	dfs(nums, visit, 0, 0);
	
	// 방문 체크 되지 않은 수 출력
	for (int i = 1; i <= MAX; ++i)
	{
		if (!visit[i])
		{
			cout << i << '\n';
			break;
		}
	}

	return 0;
}

 

방법 2: 비트마스크

#include <iostream>
#include <vector>

using namespace std;

const int MAX = 100000 * 20;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	// 입력
	int N;
	cin >> N;
	vector<int> nums(N);
	for (int i = 0; i < N; ++i)
	{
		cin >> nums[i];
	}

	// 비트마스크로 가능한 부분집합의 합 모두 구하기
	vector<bool> visit(MAX + 1);
	for (int i = 1; i < (1 << N); ++i)
	{
		int sum = 0;
		for (int j = 0; j < N; ++j)
		{
			if ((1 << j) & i)
			{
				sum += nums[j];
			}
		}
		visit[sum] = true;
	}

	// 방문 체크 되지 않은 수 출력
	for (int i = 1; i <= MAX; ++i)
	{
		if (!visit[i])
		{
			cout << i << '\n';
			break;
		}
	}

	return 0;
}

 

 

 

문제에서 N <= 20으로 주어졌기 때문에 BF로 풀이 가능하다.

가능한 부분집합의 합을 모두 구해서 bool 체크를 한뒤

체크되지 않은 수를 만나면 출력하고 종료한다.

 

백트랙킹은 O(2^n)이고, 비트마스크는 O((2^n)*n) 이므로

백트랙킹이 더 빠르다.