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

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

1182번: 부분수열의 합

 

방법 1: 비트마스크

//https://www.acmicpc.net/problem/1182
#include <iostream>
#include <vector>

using namespace std;

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

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

	/*
		i : 부분집합 
		ex) 10101 : 1,3,5 번째 수를 포함하고 2,4번째 수는 포함하지 않는 부분집합 
	*/
	int cnt = 0;
	for (int i = 1; i < (1 << N); ++i)
	{
		// 현재 부분집합에 포함된 수의 합계 구하기
		int sum = 0;
		for (int j = 0; j < N; ++j)
		{
			if (i & (1 << j))
			{
				sum += nums[j];
			}
		}

		// 합계가 S와 일치하면 경우의 수 카운트
		if (sum == S)
		{
			++cnt;
		}
	}

	cout << cnt;

	return 0;
}

 

방법 2: 백트랙킹

#include <iostream>
#include <vector>

using namespace std;

int cnt;

void dfs(vector<int> &nums, vector<bool> &check, int S, int idx)
{
	// 숫자열의 끝에 도착하면
	if (idx == nums.size())
	{
		// true 체크된 숫자들 (= 부분집합) 합계 구하기
		int sum = 0;
		for (int i = 0; i < nums.size(); ++i)
		{
			if (check[i])
			{
				sum += nums[i];
			}
		}

		// 합계가 S이면 카운팅
		if (sum == S)
		{
			++cnt;
		}

		return;
	}

	// idx번째 숫자를 선택할 때
	check[idx] = true;
	dfs(nums, check, S, idx + 1);
	check[idx] = false;

	// idx번째 숫자를 선택하지 않을 때
	dfs(nums, check, S, idx + 1);
}

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

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

	// 백트랙킹으로 부분집합의 합계 구하기
	vector<bool> check(N);
	dfs(nums, check, S, 0);

	// S가 0일 경우, 아무것도 선택하지 않는 경우도 카운팅 되므로 -1
	if (S == 0) 
	{
		--cnt;
	}

	// 출력
	cout << cnt;

	return 0;
}

 

 

TIP

비트 마스크!

부분집합의 합계를 구하는 문제에서 매우 유용하다.

 

아래처럼 for문을 (1 << N)까지 돌리면 i가 1씩 증가하며 전체 부분집합을 구할 수 있다.

// 1개 이상을 선택해야 하므로 for문을 1부터 시작.
for (int i = 1; i < (1 << N); ++i)
{
	...
}

 

예시)

i 가 1일 때 : 00001 - 1번째 숫자만 포함

i 가 5일 때 : 00101 - 1, 3번째 숫자만 포함

i 가 31일 때 : 11111 - 모든 숫자 포함