두 배열의 합 2143번 [백준]

두 배열의 합 2143번 [백준]

이번에 풀은 문제는 아이디어성 문제 였습니다.

두 배열의 부분합이 t값이 나오면 되는 문제입니다.

 

이 경우 또한 전체탐색으로 t값이 나오는 경우의 수를 찾기에는 시간복잡도를 초과하게 됩니다.

따라서 아이디어의 핵심은 각 배열을 통해 부분합을 모두 저장한 배열을 미리 만들어 두는 겁니다.

 

그 뒤는 부분합 배열을 통해 bianry search을 응용한 함수 upper_bound와 lower_bound을 통해 구하면 되는 간단한 문제였습니다.

 

vector<ll> A;
vector<ll> B;
ll t, n, m, ans = 0;// ll is long long

void solve() {
	cin >> t >> n;
	A = vector<ll>(n);
	for (ll& x : A)cin >> x;

	cin >> m;
	B = vector<ll>(m);
	for (ll& x : B)cin >> x;

	vector<ll> v, w;
	ll sum;

	for (ll i = 0; i < n; i++) {
		sum = A[i];
		v.push_back(sum);
		for (ll j = i+1; j < n; j++) {
			sum += A[j];
			v.push_back(sum);
		}
	}

	for (ll i = 0; i < m; i++) {
		sum = B[i];
		w.push_back(sum);
		for (ll j = i+1; j < m; j++) {
			sum += B[j];
			w.push_back(sum);
		}
	}

	sort(w.begin(), w.end());

	for (ll& x : v) {
		ll diff = t - x;
		auto lb = lower_bound(w.begin(), w.end(), diff);
		auto ub = upper_bound(w.begin(), w.end(), diff);
		ans += (ub - lb);
	}


	cout << ans << endl;
}

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