백준 2143 두 배열의 합 풀이

문제

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

&Title
2143번 - 두 배열의 합

&Question
한 배열 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] = A[1] + A[2] + B[1] = 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] 

&Input
첫째 줄에 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을 넘지 
않는 정수이다. 

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

&Example
-input
5
4
1 3 1 2
3
1 3 2

-output
7

요약

• a배열과 b배열의 부분배열의 합끼리 더해서 T가 나오는 쌍의개수를 모두 구해라

접근

• 부분배열의 합을 일단 구함
• 딕셔너리를 이용하려 했지만 메모리 제한이 64mb..(T범위가 1e9)ㅋㅋ 투포인터로 풀라 이거지!!
• 그럼 각각 포인터를 A배열 왼쪽, B배열 오른쪽에 두고 풀자

풀이

1. 부분합을 구한다. 매우 쉽다 범위를 하나씩 줄여나가주면 된다.

    // 부분 합 구하기
    for (int i = 0; i < n; ++i) {
        // 원소 최대 1e6, 최대개수 1e3이므로 int범위로 충분
        int sum = 0;
        for (int j = i; j < n; ++j) {
            sum += A[j];
            arr.push_back(sum);
        }
    }
   

2. 구한 부분합을 정렬한다.

    sort(arr.begin(), arr.end());
    sort(brr.begin(), brr.end());
   

3. 투포인터로 합이 같을때, 다를때 처리를 하면서 포인터를 옮겨준다. 특히 같은 경우엔 같은 숫자가 연속으로 있는 경우를 세서 곱해준다(사실 이거 때매 딕셔너리가 편한데 =ㅅ=)

   while (low < arr.size() && high >= 0) {
    int add = arr[low] + brr[high];
   
    if (add < t) ++low; // 합이 작은 경우 왼쪽 움직여줌
    // 같은 경우! 합이 같은 경우 세서 곱해줌
    else if (add == t) {
        // 최대 부분배열의 수 1~1000까지의합 (500*1001) -> 제곱하면 250,500,250,000‬ int범위 넘음 따라서 (long long)a*b 해주거나 a,b를 long long 자료형으로 선언
        long long a = 1, b = 1;
   
        while (low < arr.size() - 1 && arr[low] == arr[low + 1]) {
            ++low, ++a;
        }
        while (high >= 1 && brr[high] == brr[high - 1]) {
            --high, ++b;
        }
        result += a * b;
        // 둘중 암거나 한칸 움직여줌
        ++low;
    }
    else --high; // 합이 큰 경우 오른쪽을 움직여줌
   }
   

틀렸던 이유

• a, b의 범위가 int범위내인건 알고 있었는데 곱할때 범위가 넘는다는걸 생각을 못했다..

소스

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

int t, n, m;
int A[1000], B[1000];
vector<int> arr, brr;

int main() {
	ios::sync_with_stdio(false);
	cin >> t;
	cin >> n;
	arr.reserve(n * n);
	for (int i = 0; i < n; ++i)
		cin >> A[i];

	// 부분 합 구하기
	for (int i = 0; i < n; ++i) {
		// 원소 최대 1e6, 최대개수 1e3이므로 int범위로 충분
		int sum = 0;
		for (int j = i; j < n; ++j) {
			sum += A[j];
			arr.push_back(sum);
		}
	}
	cin >> m;
	brr.reserve(m * m);
	for (int i = 0; i < m; ++i)
		cin >> B[i];

	for (int i = 0; i < m; ++i) {
		int sum = 0;
		for (int j = i; j < m; ++j) {
			sum += B[j];
			brr.push_back(sum);
		}
	}

	sort(arr.begin(), arr.end());
	sort(brr.begin(), brr.end());
	long long result = 0;

	int low = 0, high = brr.size() - 1;

	// 투 포인터가 범위 벗어날때까지 계속
	while (low < arr.size() && high >= 0) {
		int add = arr[low] + brr[high];

		if (add < t) ++low; // 합이 작은 경우 왼쪽 움직여줌
		// 같은 경우! 합이 같은 경우 세서 곱해줌
		else if (add == t) {
			// 최대 부분배열의 수 1~1000까지의합 (500*1001) -> 제곱하면 250,500,250,000‬ int범위 넘음 따라서 (long long)a*b 해주거나 a,b를 long long 자료형으로 선언
			long long a = 1, b = 1;

			while (low < arr.size() - 1 && arr[low] == arr[low + 1]) {
				++low, ++a;
			}
			while (high >= 1 && brr[high] == brr[high - 1]) {
				--high, ++b;
			}
			result += a * b;
			// 둘중 암거나 한칸 움직여줌
			++low;
		}
		else --high; // 합이 큰 경우 오른쪽을 움직여줌
	}

	cout << result << endl;
	return 0;
}