BOJ 2143 - 두 배열의 합

2143번: 두 배열의 합 (acmicpc.net)

2143번: 두 배열의 합

 

처음에 너무 많이 삽질을 했다

a와 b의 모든 누적합을 저장하여 이를 lower_bound와 upper_bound로 중복되는 값들을 제거하면 구하는 문제이다.

 

부배열은 순서대로 이어지기 때문에, 1, 3, 4 나 2, 5, 7 이런 배열은 포함되지 않는다.

 

a의 모든 경우의 누적 합들 (a[0], a[0]+a[1], a[0]+a[1]+a[2], )과 b의 모든 경우의 누적 합들을 각 배열 aSum과 bSum에 저장하고, 두 배열 중 합이 T인 값들의 경우를  더하면 된다. 또한 고려해야 할 점은 중복 값이 있을 수 있으므로, lower_bound와 upper_bound로 중복되는 값들을 제거해야 한다.

 

내가 삽질한 부분은 aSum과 bSum을 어떻게 빠르게 확인할까?였다.

단순히 이중for문으로 돌면 시간초과가 뜰 것이라고 생각했다.

그래서 a와 b를 투 포인터를 이용해 구하려고 했다.

그런데 생각을 해보니 N과 M은 1000이 맥스값이여서 이중 for문을 돌려도 시간초과를 만나지 않을 것 같다는 생각이 들었다. 결과는 성공적...

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

#define ll long long

ll t, n, m, res;
vector<ll> a;
vector<ll> b;
vector<ll> aSum;
vector<ll> bSum;


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> t;
	cin >> n;
	for (int i = 0; i < n; i++) {
		ll tmp; cin >> tmp;
		a.push_back(tmp);
	}

	cin >> m;
	for (int i = 0; i < m; i++) {
		ll tmp; cin >> tmp;
		b.push_back(tmp);
	}



	for (int i = 0; i < n; i++) { 
		int tmp = a[i];
		aSum.push_back(tmp);
		for (int j = i+1; j < n; j++) {
			tmp += a[j];
			aSum.push_back(tmp);
		}
	}

	for (int i = 0; i < m; i++) {
		int tmp = b[i];
		bSum.push_back(tmp);
		for (int j = i+1; j < m; j++) {
			tmp += b[j];
			bSum.push_back(tmp);
		}
	}

	
	sort(aSum.begin(), aSum.end());
	sort(bSum.begin(), bSum.end());

	ll l = 0;
	ll r = bSum.size() - 1;

	for (int i = 0; i < aSum.size(); i++) {
		int tmp = t - aSum[i];
		
		ll lower = lower_bound(bSum.begin(), bSum.end(), tmp) - bSum.begin();
		ll upper = upper_bound(bSum.begin(), bSum.end(), tmp) - bSum.begin();
		
		res += (upper - lower);
	}
	cout << res;
}