[알고리즘] C++ 백준 2143 두 배열의 합

백준 2143

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

2143번: 두 배열의 합

풀이 전 나의 생각

배열 A, B가 주어질 때 A의 부 배열 합에 B의 부 배열 합을

더해서 T가  되는 모든 부 배열 쌍의 개수를 구해야 한다.

 

조건

- 부 배열은 A[i], A[i+1], …, A[j-1], A[j] (단, 1 ≤ i ≤ j ≤ n)

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

- T(-1,000,000,000 ≤ T ≤ 1,000,000,000)

- n(1 ≤ n ≤ 1,000)

- m(1 ≤ m ≤ 1,000)

- 배열 원소는 절댓값이 1,000,000을 넘지 않는 정수

 

과정

1. 부 배열의 합을 더하기 위해 2중 for문을 한 횟수 (1000 * 999...) + 합을 판단하는 for문

이런 식으로 문제를 해결하면 계산 횟수가 너무 많아지기 때문에 이분탐색을 사용하여 풀이를 진행해야한다.

 

2. 배열의 원소값은 100만이 넘지 않지만 100만 * 부 배열 합의 경우의 수(1000 * 999...) 를 하면

int형은 가볍게 넘기기 때문에 합을 담당하는 변수는 더 큰 데이터 타입을 사용해야한다.

 

3. 부 배열의 조건은 A[i], A[i+1], …, A[j-1], A[j] 이며, 부 배열의 합은  A[i]+…+A[j]를 의미한다는 것은

부배열의 합은 무조건 연속된 합이 되어야 한다는 의미다.

ex) B 부 배열 (1, 2, 3, 4) -> 1 + 2,  1 + 2 + 3, 2 + 3, 3 + 4... (O)-> 1 + 3, 1 + 4, 1 + 2 + 4, 2 + 4...(X)

 

1. 부 배열의 연속된 합을 미리 구해준다.

for (int i = 0; i < n; i++)
	{
		long long sum = 0;
		for (int j = i; j < n; j++)
		{
			sum += n_vec[j];
			n_sum.push_back(sum);
		}
	}

	for (int i = 0; i < m; i++)
	{
		long long sum = 0;
		for (int j = i; j < m; j++)
		{
			sum += m_vec[j];
			m_sum.push_back(sum);
		}
	}

연속된 합을 미리 구해놓으면 나중에 이분탐색을 진행 할 때

추가로 합을 더하면서 진행할 필요가 없어지게된다.

 

2. 구해놓은 A 부 배열 합 + B 부 배열 합이 T가 되는 경우를 구한다.

for (int i = 0; i < n_sum.size(); i++)
	{
		int target = T - n_sum[i];
		
		auto lower = lower_bound(m_sum.begin(), m_sum.end(), target);
		auto upper = upper_bound(m_sum.begin(), m_sum.end(), target);
		ans += (upper - lower);
	}

목표로 하는 T값에서 이전에 구해놓은 A 부 배열의 합을 빼면 현재

T를 만들 수 있는 나머지 값이 나오게 된다.

 

B 부 배열의 합을 구해놓은 m_sum 벡터를 이분탐색하며 T를 만들 수 있는 나머지 값이

m_sum 벡터에 존재한다면 경우의 수를 upper - lower로 모두 구해준다.

 

upper - lower를 하는 이유는 찾고자 하는 요소의 시작(lower)과 끝의 다음(upper)을 반환하기 때문에 

둘 을 빼주면 찾고자 하는 모든 요소의 개수를 구할 수 있다.

 

마지막으로 구한 값을 최종값에 더해주면 문제에서 요구하는 답을 구해낼 수 있다.

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int T, n, m;
	long long ans = 0;

	cin >> T >> n;

	vector<int>n_vec(n);
	
	for (int i = 0; i < n; i++)
	{
		cin >> n_vec[i];
	}

	cin >> m;

	vector<int>m_vec(m);

	for (int i = 0; i < m; i++)
	{
		cin >> m_vec[i];
	}

	vector<long long>n_sum, m_sum;

	for (int i = 0; i < n; i++)
	{
		long long sum = 0;
		for (int j = i; j < n; j++)
		{
			sum += n_vec[j];
			n_sum.push_back(sum);
		}
	}

	for (int i = 0; i < m; i++)
	{
		long long sum = 0;
		for (int j = i; j < m; j++)
		{
			sum += m_vec[j];
			m_sum.push_back(sum);
		}
	}

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

	for (int i = 0; i < n_sum.size(); i++)
	{
		int target = T - n_sum[i];
		
		auto lower = lower_bound(m_sum.begin(), m_sum.end(), target);
		auto upper = upper_bound(m_sum.begin(), m_sum.end(), target);
		ans += (upper - lower);
	}

	cout << ans;
}