[BOJ] 1182. 부분수열의 합 (backtracking, bruteforcing)

Silver II

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

1182번: 부분수열의 합

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

 

input:

• 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000)
• 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

output:

• 첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

 

---

Idea :

• 부분수열 중 그 수열의 원소의 합이 S가 되는 경우의 수를 구하는 문제
• 부분수열 구하기
  1. 비트마스킹을 이용해 부분집합 구하기
  2. dfs를 이용해 조합 구하기

Code 1:  using Bitmask

• 비트마스킹을 이용해 부분집합/부분수열 구하기
  • 부분집합의 개수 = 2^N - 1 = (1 << N) - 1
  • 0부터 (1 << N) - 1 까지로 부분집합을 표현할 수 있음 (예시 더보기 참고)

ex) N = 3, {a, b, c}

부분집합	{}	{a}	{b}	{c}	{a, b}	{a, c}	{b, c}	{a, b, c}
비트마스크	000	001	010	100	011	101	110	111
10진수	0	1	2	4	3	5	6	7

 

#include <iostream>

using namespace std;

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	// freopen("input.txt", "rt", stdin);

	int N, S;
	int arr[20] = {};

	/* input */
	cin >> N >> S;
	for (int i=0; i<N; i++) cin >> arr[i];

	/* solve */
	int ans = 0;
	for (int seq=1; seq < (1 << N); seq++) {
		int sum = 0;
		for (int i=0; i<N; i++) {
			if ((seq & (1 << i)) != 0) sum += arr[i];
		}
		if (sum == S) ans++;
	}

	/* print answer */
	cout << ans << "\n";
}

 

Code 2:  using DFS

• 수열의 각 원소는 부분수열에 포함되거나 포함되지 않을 수 있음
• 길이가 N인 수열로 만들 수 있는 부분수열의 개수는 2^N개
• 가능한 모든 부분수열에 대해 원소의 합을 구하고 S와 같은 부분수열의 개수가 답이 됨

#include <iostream>

using namespace std;

int N, S;
int arr[20] = {};
int ans = 0;

void dfs (int depth, int sum) {
	if (depth == N) return;
	if (sum + arr[depth] == S) ans++;

	dfs(depth + 1, sum + arr[depth]);   // depth 번째 원소를 부분수열에 포함하는 경우
	dfs(depth + 1, sum);                // depth 번째 원소를 부분수열에 포함하지 않는 경우
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	// freopen("input.txt", "rt", stdin);
    
	/* input */
	cin >> N >> S;
	for (int i=0; i<N; i++) cin >> arr[i];

	/* solve */
	dfs(0, 0);
    
	/* print answer */
	cout << ans << "\n";
}

---

Result : 

code 1) 메모리: 2020 KB,  시간: 60 ms

code 2) 메모리: 2020 KB,  시간: 0 ms 

 

Review :

• 부분집합 구하는 문제와 유사하기 때문에 dfs보다 비트마스킹을 사용하는 것이 더 효율적이라고 판단했었음
• 그러나 실제로는 dfs를 이용하는 것이 시간복잡도 관점에서 훨씬 효율적
• 비트마스킹을 이용할 경우 2^N개의 부분집합에 대해 부분수열의 원소 합을 구하기 위해 N 번의 반복문을 실행 → O(N*2^N)
• dfs를 이용할 경우 2^N 번의 dfs가 호출됨 → O(2^N)