C++[백준]2143번 두 배열의 합

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

2143번: 두 배열의 합

 

 

솔루션

---

처음에 어떻게 접근을 해야 하지.. 생각을 하다가 검색을 했는데, 각 배열의 모든 합을 구한 뒤 정렬, 이진 검색을 통해서 푼다는 것을 알게되었다.

 

먼저 배열 A와 B를 입력을 다 받은 후에

 

이중 for문을 통해서 모든 배열의 부분합을 벡터에 담았다.

 

그리고 둘다 정렬을 해 주고

 

배열 A를 순차적으로 돌면서 

T의 값에서 배열 A의 값을 빼 준뒤, B배열에서 

lower_bound - upper_bound를 해 주고 

그 차이를 모두 더해서 출력하였다.

 

정수 범위로는 오버플로우가 날 수 있으니, long long 을 권장한다.

 

 

 

코드

---

#define ll long long int
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int T;
int N, M;
ll valA[1002], valB[1002];
vector<ll> arrA;
vector<ll> arrB;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> T;

	cin >> N;
	for (int i = 0; i < N; i++) cin >> valA[i];
	for (int i = 0; i < N; i++) {
		ll sum = 0;
		for (int j = i; j < N; j++) {
			sum += valA[j];
			arrA.push_back(sum);
		}
	}
	
	cin >> M;
	for (int i = 0; i < M; i++) cin >> valB[i];
	for (int i = 0; i < M; i++) {
		ll sum = 0;
		for (int j = i; j < M; j++) {
			sum += valB[j];
			arrB.push_back(sum);
		}
	}

	sort(arrA.begin(), arrA.end());
	sort(arrB.begin(), arrB.end());
	
	ll cnt = 0;
	for(int i=0;i<arrA.size();i++){
		ll tmp = T - arrA[i];
		
		ll front = lower_bound(arrB.begin(), arrB.end(), tmp) - arrB.begin();
		ll end = upper_bound(arrB.begin(), arrB.end(), tmp) - arrB.begin();
		
		if (front != end) {
			cnt += end - front;
		}
	}
	cout << cnt << "\n";
}