브루트 포스/브루트포스(재귀)
부분수열의 합 (재귀, 비트마스크)
4gats
2023. 3. 21. 19:53
https://www.acmicpc.net/problem/1182
1182번: 부분수열의 합
첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.
www.acmicpc.net
크기가 양수인 부분수열이므로 2 ^ N - 1개
N <= 20이므로 경우의 수가 크지 않다
시간복잡도 O(2 ^ N)
|
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
30
31
32
33
34
35
36
37
38
39
|
#include <iostream>
#include <vector>
using namespace std;
int n;
int m;
int ans = 0;
void go(vector<int> &a, int index, int sum)
{
if (index == n)
{
if (sum == m)
ans += 1;
return;
}
go(a, index + 1, sum + a[index]);
go(a, index + 1, sum);
}
int main()
{
cin >> n >> m;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
go(a, 0, 0);
// 크기가 양수인 부분수열이므로
if (m == 0)
ans -= 1;
cout << ans << '\n';
return 0;
}
|
cs |
https://www.acmicpc.net/problem/14225
14225번: 부분수열의 합
수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들
www.acmicpc.net
bool 타입 배열을 쓰자 -> size는 20 * 100000 + 10
|
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
int m;
int ans = 0;
int d[20];
bool c[20*100000 + 10];
void go(int index, int sum)
{
if (index == n)
{
c[sum] = true;
return;
}
go(index + 1, sum + d[index]);
go(index + 1, sum);
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
cin >> d[i];
go(0, 0);
for (int i = 1; ; i++)
{
if (c[i] == false)
{
cout << i << '\n';
break;
}
}
return 0;
}
|
cs |
고른다 안고른다는 비트마스크로 풀 수 있다!
|
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
bool c[20 * 100000 + 10];
int a[20];
int n;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
// 모든 부분 집합
for (int i = 0; i < (1 << n); i++)
{
int sum = 0;
for (int j = 0; j < n; j++)
{
if (i & (1 << j))
{
sum += a[j];
}
}
c[sum] = true;
}
for (int i = 1; ; i++)
{
if (c[i] == false)
{
cout << i << '\n';
break;
}
}
return 0;
}
|
cs |