백준 1208 부분수열의 합 2 (c++) : 피너클

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

1208번: 부분수열의 합 2

이진탐색 문제다.

현재 n이 40이니 모든 부분수열을 구하면 2 ^ 40 =  1,099,511,627,776만큼의 수열을 구해야한다.

그런 2 ^ 20짜리 부분수열 2개를 구할것이다.

long long n, s;
long long arr[41];
vector<long long> first, second;
vector<long long> ::iterator a, b;

선언한 변수들이다. first와 second에는 부분수열들이 들어갈것이고 a, b는 이진탐색에 사용할것이다.

cin >> n >> s;
for (int i = 0; i < n; i++) cin >> arr[i];
make(0, 0, n / 2);
make(n / 2, 0, n);

값을 입력받고 make함수를 돌려준다

make함수는 (현재위치, 합, 마지막)을 입력받는다.

void make(long long idx, long long sum, long long l) {
	if (idx == l) {
		if (l == n / 2) first.push_back(sum);
		else second.push_back(sum);
		return;
	}
	make(idx + 1, sum + arr[idx], l);
	make(idx + 1, sum, l);
}

만약 idx == l이라면 마지막까지 왔다는 뜻이다.

l이 n/2라면 sum을 first에 넣고 아니며 second에 넣는다.

그후 현재 값을 추가한 make와 추가하지 않은 make를 돌린다.

함수를 전부 돌리면 first와 second에 n의 절반 크기의 부분수열이 들어가게된다.

sort(first.begin(), first.end());
sort(second.begin(), second.end());
long long ans = 0;

이제 두 벡터를 정렬한뒤 ans를 준비한다. ans에는 정답이 들어갈것이다.

for (int i = 0; i < second.size(); i++) {
	a = lower_bound(first.begin(), first.end(), s - second[i]);
	b = upper_bound(first.begin(), first.end(), s - second[i]);
	ans += b - a;
}

second의 크기 만큼 반복한다.

lower_bound는 배열에서 목표값 이상의 값의 위치를 반환하고

upper_bound는 배열에서 목표값 초과의 값의 위치를 반환한다.

arr = [10, 20, 30, 30, 30, 40, 50] 배열이 있다고 가정하고 이 안에서 30이 몇개가 있는지를 확인해햐한다 해보자.

lower_bound(arr, arr + 7, 30)을 하면 30 이상의 값이 위치한 첫번째 값인 2가 리턴되고

upper_bound(arr, arr + 7, 30)을 하면 30 초과의 값이 위치한 첫번째 값인 5가 리턴된다.

이 둘을 빼면 3이 나오고 이것이 배열에서 30의 개수이다.

arr = [10, 20, 30, 30, 30, 40, 50] 배열에서 25를 찾는다면 어떻게 될까

lower_bound(arr, arr + 7, 25)을 하면 25 이상의 값이 위치한 첫번째 값인 2 (arr[2] = 30) 가 리턴되고

upper_bound(arr, arr + 7, 25)을 하면 25 초과의 값이 위치한 첫번째 값인 2 (arr[2] = 30) 가 리턴되

이 둘을 빼며 0이 나오고 이것이 배열에서 25의 개수가 된다.

b - a 는 first배열에서 s-seound[i]가 몇개인지를 반환한다.

if (s == 0) ans -= 1;
cout << ans << endl;

s가 0이면 ans-1을 한다. 크기가 양인 부분수열중 구해야 하는데

아무것도 고르지 않은 부분수열이 포함되어있기 때문이다.

그후 ans를 출력한다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

long long n, s;
long long arr[41];
vector<long long> first, second;
vector<long long> ::iterator a, b;

void make(long long idx, long long sum, long long l) {
	if (idx == l) {
		if (l == n / 2) first.push_back(sum);
		else second.push_back(sum);
		return;
	}
	make(idx + 1, sum + arr[idx], l);
	make(idx + 1, sum, l);
}

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

	cin >> n >> s;
	for (int i = 0; i < n; i++) cin >> arr[i];
	make(0, 0, n / 2);
	make(n / 2, 0, n);
	sort(first.begin(), first.end());
	sort(second.begin(), second.end());
	long long ans = 0;
	for (int i = 0; i < second.size(); i++) {
		a = lower_bound(first.begin(), first.end(), s - second[i]);
		b = upper_bound(first.begin(), first.end(), s - second[i]);
		ans += b - a;
	}
	if (s == 0) ans -= 1;
	cout << ans << endl;
}

 

전체코드다.