2143번: 두 배열의 합

문제

한 배열 A[1], A[2], …, A[n]에 대해서, 부 배열은 A[i], A[i+1], …, A[j-1], A[j] (단, 1 ≤ i ≤ j ≤ n)을 말한다.

이러한 부 배열의 합은 A[i]+…+A[j]를 의미한다.

각 원소가 정수인 두 배열 A[1], …, A[n]과 B[1], …, B[m]이 주어졌을 때,

A의 부 배열의 합에 B의 부 배열의 합을 더해서 T가 되는 모든 부 배열 쌍의 개수를 구하는 프로그램을 작성하시오.

 

 

예를 들어 A = {1, 3, 1, 2}, B = {1, 3, 2}, T=5인 경우, 부 배열 쌍의 개수는 다음의 7가지 경우가 있다.

 

T(=5)

= A[1] + B[1] + B[2] (1+1+3 = 5)

= A[1] + A[2] + B[1] (1+3+1 =5)

= A[2] + B[3]

= A[2] + A[3] + B[1]

= A[3] + B[1] + B[2]

= A[3] + A[4] + B[3]

= A[4] + B[2]

입력

첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다음 줄에 m개의 정수로 B[1], …, B[m]이 주어진다. 각각의 배열 원소는 절댓값이 1,000,000을 넘지 않는 정수이다.

출력

첫째 줄에 답을 출력한다. 가능한 경우가 한 가지도 없을 경우에는 0을 출력한다.

예제 입력 1

5 -->-1,000,000,000 ≤ T ≤ 1,000,000,000 --> 목표값

4 -->1 ≤ n ≤ 1,000 -->A

1 3 1 2

3-->1≤m≤1,000 -->B

1 3 2

예제 출력 1

7

 

---

풀이 

: 1. 연속된 부분집합의 합 집합을 구하기  ( 이중 포문) --> 1000000 개 *2  -->O(N^2)

2. A 부분 집합의 합 들  B 부분 집합의 합들 --> 화살표가리키면서 T값 찾기 --> ans 값 도출

 

--> 틀렸음  1<=N,M<=1000 라서 비트마스크로는 할수 없음 (비트 부족함)

 

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

 

이중 포문을 이용해서 모든 연속된 배열을 만들어 낸다.

 

***

equal_range( v.begin(), v.end(), 찾고 싶은 값); 

함수를 사용한다.

--> return type 은  pair< std::vector<int> ::iterator, std::vector<int>::iterator> 이다.

이 함수는 binary search 한다. 

binary search 는 upper_bound 와 lower_bound 가 있다.

pair .first 에는 lower_bound 인덱스 // pair.second에는 upper_bound 인덱스 값을 리턴한다.

따라서, 두값의 차로 목표하는 값이 몇개 있는지 한번에 알수 있다. (선 정렬해야됨)

--> lower_bound 는  목표하는 값 보다 크거나 같은 값 중 제일 작은거

--> upper_bound 는 목표하는 값 보다 큰 값 중 제일 작은거

 

---

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
	int t;
	cin >> t;
	int n;
	cin >> n;
	// 배열 받음
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int m;
	cin >> m;
	vector<int> b(m);
	for (int i = 0; i < m; i++) {
		cin >> b[i];
	}

	// 부분 배열의 합의 집합
	vector<int> x;
	for (int i = 0; i < n; i++) {
		int sum = 0;
		for (int j = i; j < n; j++) {
			sum += a[j];
			x.push_back(sum);
		}
	}

	vector<int> y;
	for (int i = 0; i < m; i++) {
		int sum = 0;
		for (int j = i; j < m; j++) {
			sum += b[j];
			y.push_back(sum);
		}
	}
	
	//정렬
	sort(x.begin(), x.end());
	sort(y.begin(), y.end());

	// x를 기준으로 y에서 값을 찾음.
	long long ans = 0;
	for (int i = 0; i < x.size(); i++) {
		pair<std::vector<int> ::iterator , std::vector<int> ::iterator> p = equal_range(y.begin(), y.end(), t - x[i]);
		ans += p.second - p.first;
	}
	cout << ans << '\n';

	return 0;
}