백준 온라인 저지
백준 1182: 부분집합의 합
dev_doyle
2018. 7. 29. 21:53
부분집합의 합 문제 재귀함수를 이용한 브루트 포스로 문제를 해결했다. 시간 복잡도는 재귀함수가 2번의 재귀함수를 호출하고 문제의 크기를 줄이지는 못하므로 divide and conquer와는 다르다. 결과적으론 O(2^n)의 시간복잡도를 가진다. 하지만 n이 20미만이니 충분히 계산가능하다. 풀이할 것이 많지는 안지만 index를 증가시켜가며 현재의 인덱스가 가르키는 집합의 원소를 포함하느냐 하지 않느냐를 모두 재귀함수로 만들어 모든 부분집합의 경우의 수를 만들 수 있다. 한 가지 주의사항은 이 go 함수는 공집합, 즉 아무 원소도 포함하지 않을 때의 모든 원소의 합 말이 이상한데 즉 공집합을 포함하고 있어서 만약 구하고자 하는 값이 0이라면 go 에서 구한 것에서 1 빼줘야한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
using namespace std;
int ans, n;
int set[32];
int go(int index, int sum){
if (index == n && sum == ans){
return 1;
}
if (index == n && sum != ans){
return 0;
}
int now = 0;
now += go(index + 1, sum + set[index]);
now += go(index + 1, sum);
return now;
}
int main(){
cin >> n >> ans;
int out_ans = 0;
for (int i = 0; i < n; ++i){
cin >> set[i];
}
out_ans = go(0, 0);
if (ans == 0)
--out_ans;
cout << out_ans << endl;
return 0;
}