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

1. 문제

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

2143번: 두 배열의 합

 

2. 알고리즘 분류

• 자료 구조
• 이분 탐색
• 누적 합

 

3. 소스 코드

Key Point)
1. 두 A, B의 배열의 누적 합들을 모두 구한다.
2. B를 오름차순으로 정렬한 후, 이진 탐색을 하면 빠르게 해답을 찾을 수 있다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int A[10005], B[10005];
vector<int> sum_a, sum_b;

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

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

	cin >> T;
	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> A[i];

	cin >> m;

	for (int i = 0; i < m; i++)
		cin >> B[i];

	// A로 만들 수 있는 부분합 구하기
	for (int i = 0; i < n; i++)
	{
		int sum = A[i];
		sum_a.push_back(sum);

		for (int j = i + 1; j < n; j++)
		{
			sum += A[j];
			sum_a.push_back(sum);
		}
	}

	// B로 만들 수 있는 부분합 구하기
	for (int i = 0; i < m; i++)
	{
		int sum = B[i];
		sum_b.push_back(sum);

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

	// B 부분합을 오름차순 정렬(이진 탐색하기 위한 용도)
	sort(sum_b.begin(), sum_b.end());

	// 각 A 부분합에 대해서 차이값을 이진 탐색을 통해 찾기
	for (auto item : sum_a)
	{
		int diff = T - item;
		auto ub = upper_bound(sum_b.begin(), sum_b.end(), diff);
		auto lb = lower_bound(sum_b.begin(), sum_b.end(), diff);
		ans += (ub - lb);
	}

	cout << ans;

	return 0;
}

 

4. 유용한 문법 및 알고리즘

 1) 이분 탐색 (Binary Search)

• 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법

	// 각 A 부분합에 대해서 차이값을 이진 탐색을 통해 찾기
	for (auto item : sum_a)
	{
		int diff = T - item;
		auto ub = upper_bound(sum_b.begin(), sum_b.end(), diff);
		auto lb = lower_bound(sum_b.begin(), sum_b.end(), diff);
		ans += (ub - lb);
	}