[백준 알고리즘][BOJ][C++] 이분 탐색(binary search) - 1208번 부분수열의 합 2

안녕하세요~

 

이번시간에는 1208번 부분수열의 합 2 문제를 풀어보려고 합니다.

 

www.acmicpc.net/problem/1208

1208번: 부분수열의 합 2

 

명심하셔야 될 것은 일단 문제를 풀기 전에 코딩을 먼저 시작하지 마시고, 반드시 연습장으로 생각을 정리하고! 이 후에 생각이 맞는 것 같다고 확신이 되면 그 때 코딩을 시작하세요. 코드를 작성하면서 문제를 풀게되면 정리가 안된 상태기 때문에 코드 수정이 잦아지고, 정신이 없어지게 됩니다ㅠㅠ

그러니 반드시 노트에 어떻게 풀 것인지에 대한 정리를 다 하시고 코딩을 시작하시기 바랍니다!!

​

binary search 공부에 좋은 문제입니다.

 

문제

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

입력

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

출력

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

예제 입력 1 

5 0
-7 -3 -2 5 8

예제 출력 1

1

정답 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, S;
int arr[40];
vector<int> first_half_array;
vector<int> second_half_array;
 
void bfs_first_half(int count, int sum)
{
	if (count == N/2)
	{
		first_half_array.push_back(sum);
		return;
	}
	//select
	bfs_first_half(count + 1, sum + arr[count]);
	//no select
	bfs_first_half(count + 1, sum);
 
}
void bfs_second_half(int count, int sum)
{
	if (count == N)
	{
		second_half_array.push_back(sum);
		return;
	}
	//select
	bfs_second_half(count + 1, sum + arr[count]);
	//no select
	bfs_second_half(count + 1, sum);
}
void solve()
{
	int count = 0;
	int sum = 0;
	bfs_first_half(count, sum);
	count = N / 2;
	sum = 0;
	bfs_second_half(count, sum);
 
	//N/2로 나눈 두개의 배열의 합을 모두 구했음
	//sort(first_half_array.begin(), first_half_array.end());
	sort(second_half_array.begin(), second_half_array.end());
	long long answer = 0;
	for (int i = 0; i < first_half_array.size(); i++)
	{
		int val = S - first_half_array[i];
		int lo = lower_bound(second_half_array.begin(), second_half_array.end(), val) - second_half_array.begin();
		int hi = upper_bound(second_half_array.begin(), second_half_array.end(), val) - second_half_array.begin();
		answer = answer + (hi - lo);
	}
	if (S == 0) {
		--answer;
	}
	cout << answer << endl;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> S;
	int val;
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	solve();
}