백준 2143 두 배열의 합 (c++) : 피너클

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

2143번: 두 배열의 합

이진탐색을 이용하는 문제다.

각 배열의 부 배열을 만들고 그들을 이용해 이진탐색으로 답을 구한다.

int t, n, m;
int a[1001], b[1001];
vector<int> as, bs;
vector<int> ::iterator f, s;

선언하는 변수다. as, bs는 부배열이 들어갈것이고 f, s는 이진탐색에 이용할것이다.

void make_sumA(int idx) {
	if (idx == n) return;
	int sum = 0;
	for (int i = idx; i < n; i++) {
		sum += a[i];
		as.push_back(sum);
	}
	make_sumA(idx + 1);
}

a의 부배열을 구하는 함수다. 

arr[0], arr[0] + arr[1], arr[0] + arr[1] + arr[2], ... , arr[0] + ... +arr[n-1]을 as에 넣는뒤

arr[1], arr[1] + arr[2], arr[1] + arr[2] + arr[3], ... , arr[1] + ... +arr[n-1]을 as에 넣고를 계속 반복한다.

처음 시작이 n이 되면 바로 함수를 종료한다.

void make_sumB(int idx) {
	if (idx == m) return;
	int sum = 0;
	for (int i = idx; i < m; i++) {
		sum += b[i];
		bs.push_back(sum);
	}
	make_sumB(idx + 1);
}

b도 똑같이 해준다.

cin >> t;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
make_sumA(0);
cin >> m;
for (int i = 0; i < m; i++) cin >> b[i];
make_sumB(0);
sort(as.begin(), as.end());
sort(bs.begin(), bs.end());

이제 main함수에서 값들을 입력받고 부 배열을 만든뒤 전부 정렬한다.

long long ans = 0;
for (int i = 0; i < as.size(); i++) {
	int now = as[i];
	f = lower_bound(bs.begin(), bs.end(), t - now);
	s = upper_bound(bs.begin(), bs.end(), t - now);
	ans += s - f;
}
cout << ans << endl;

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의 개수가 된다.

s - f 는 bs배열에서 t - now[i]가 몇개인지를 반환한다.

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

using namespace std;

int t, n, m;
int a[1001], b[1001];
vector<int> as, bs;
vector<int> ::iterator f, s;

void make_sumA(int idx) {
	if (idx == n) return;
	int sum = 0;
	for (int i = idx; i < n; i++) {
		sum += a[i];
		as.push_back(sum);
	}
	make_sumA(idx + 1);
}
void make_sumB(int idx) {
	if (idx == m) return;
	int sum = 0;
	for (int i = idx; i < m; i++) {
		sum += b[i];
		bs.push_back(sum);
	}
	make_sumB(idx + 1);
}

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

	cin >> t;
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];
	make_sumA(0);
	cin >> m;
	for (int i = 0; i < m; i++) cin >> b[i];
	make_sumB(0);
	sort(as.begin(), as.end());
	sort(bs.begin(), bs.end());
	long long ans = 0;
	for (int i = 0; i < as.size(); i++) {
		int now = as[i];
		f = lower_bound(bs.begin(), bs.end(), t - now);
		s = upper_bound(bs.begin(), bs.end(), t - now);
		ans += s - f;
	}
	cout << ans << endl;
}

전체코드다.