백준 2143(두 배열의 합) c++

문제

2143번: 두 배열의 합

내가 접근한 방식 : 투 포인터, 재귀함수로 구현한 트리

내가 놓친 부분 : 부배열(연속된 배열의 합)

나는 연속되지않은 배열의 합도 고려함

 

배열이 두개 주어지면 두 배열의 부배열(연속된 배열의 합)의 합이 t와 같은 개수를 구하면 되는 문제입니다.

배열의 크기가 최대 1000이므로 배열의 부배열들을 구하는데 1000 * 1000 = 1000000이므로 무난합니다.

vector<ll>sum_a;
for (int i = 0; i < n ; i++) {
	ll sum = a[i];
	sum_a.push_back(sum);
	for (int j = i + 1; j < n; j++) {
		sum += a[j];
		sum_a.push_back(sum);
	}
}

vector<ll>sum_b;
for (int i = 0; i < m ; i++) {
	ll sum = b[i];
	sum_b.push_back(sum);
	for (int j = i + 1; j < m; j++) {
		sum += b[j];
		sum_b.push_back(sum);
	}
}

 

이제 각 배열의 누적합들을 저장했기 때문에 벡터 sum_a와 sum_b의 인덱스 값을 서로 더하면서 

t값과 똑같은 것을 세면됩니다.

하지만 이렇게 구현하게 되면 시간 초과가 나게 되므로, lower_bound와 upper_bound를 응용합니다.

기준으로 sum_a를 잡고, sum_a의 크기만큼 돌면서 t - sum_a[i] 의 값이 sum_b 안에 있으면 

정답의 경우의 수 이므로 이를 세면 됩니다. 세는 방법은 lower, upper bound를 사용합니다.

sort(sum_b.begin(), sum_b.end());
ll ans = 0;

for (int i = 0; i < sum_a.size(); i++) {
	int target = t - sum_a[i];
	ans += upper_bound(sum_b.begin(), sum_b.end(), target) - lower_bound(sum_b.begin(), sum_b.end(), target);
}
cout << ans;

lower, upper_bound를 사용하기 위해서는 먼저 정렬을 해줘야합니다.

---

전체 코드입니다.

#include<iostream>
#include<string>
#include<cstring>
#include<sstream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
using ll = long long;
ll a[1001];
ll b[1001];
int n;
int m;
int main() {
	int t;
	cin >> t;

	cin >> n;
	for (int i = 0; i < n; i++)cin >> a[i];

	cin >> m;
	for (int i = 0; i < m; i++)cin >> b[i];

	vector<ll>sum_a;
	for (int i = 0; i < n ; i++) {
		ll sum = a[i];
		sum_a.push_back(sum);
		for (int j = i + 1; j < n; j++) {
			sum += a[j];
			sum_a.push_back(sum);
		}
	}

	vector<ll>sum_b;
	for (int i = 0; i < m ; i++) {
		ll sum = b[i];
		sum_b.push_back(sum);
		for (int j = i + 1; j < m; j++) {
			sum += b[j];
			sum_b.push_back(sum);
		}
	}

	sort(sum_b.begin(), sum_b.end());
	ll ans = 0;
	for (int i = 0; i < sum_a.size(); i++) {
		int target = t - sum_a[i];
		ans += upper_bound(sum_b.begin(), sum_b.end(), target) - lower_bound(sum_b.begin(), sum_b.end(), target);
	}
	cout << ans;
	return 0;
}