[백준]2143_두 배열의 합

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

Solved

✔ 알고리즘 분류: 이분 탐색, 누적 합
✔ 이분 탐색: 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘.
오름차순으로 정렬된 리스트의 중간 값을 임의의 값으로 선택하여 찾고자 하는 Key 값과 비교하는 방식.
✔ A와 B 배열 각각으로 만들 수 있는 부배열의 합을 미리 다 구한다.
✔ B를 정렬한다 (이분탐색(바이너리서치)을 윟0
✔ A의 원소를 하나씩 탐색하며 (T-A원소)값이 B에 몇 개 존재하는지 찾는다.

//way1: 직접구현: 반복문을 이용한 이진탐색
bool BinarySearch(int *arr, int len, int key){
    int start = 0;
    int end = len-1;
    int mid;
 
    while(end - start >= 0) {
        mid = (start + end) / 2;    //중앙 값
 
        if (arr[mid] == key) {    //key값을 찾았을때
            return true;
 
        } else if (arr[mid] > key) {   //key값이 mid의 값보다 작을때 (왼쪽으로)
            end = mid - 1;
 
        } else {  //key값이 mid의 값보다 클때 (오른쪽으로)
            start = mid + 1;
 
        }
    }
    return false;
}

//way2: binary Search STL 사용하기
#include<iostream>
#include<algorithm>
using namespace std;

int main(void){
    int n= 100;
    int arr[n];
 
    for(int i=0; i<n; i++){
        arr[i] = i;
    }
 
    cout << "exist : " << binary_search(arr, arr+n, 70) << endl;
    
    return 0;
}

//way3: lowerbound, upperbound - 일종의 이분탐색에서 파생된 함수
//lower_bound: 원하는 값 k 이상이 처음 나오는 위치
//upperbound: 원하는 값 k를 초과한 값이 처음 나오는 위치
//이번 문제의 풀이를 참고

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

vector<int> arr, brr, v1, v2;
int main() {
	int t, n, m;
	cin >> t >> n;
	arr.resize(n);
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	cin >> m;
	brr.resize(m);
	for (int i = 0; i < m; i++)
		cin >> brr[i];

	//a로 만들 수 있는 부분합
	for (int i = 0; i < n; i++) {
		int sum = arr[i];
		v1.push_back(sum);
		for (int j = i + 1; j < n; j++) {
			sum += arr[j];
			v1.push_back(sum);
		}
	}
	//b로 만들 수 있는 부분합
	for (int i = 0; i < m; i++) {
		int sum = brr[i];
		v2.push_back(sum);
		for (int j = i + 1; j < m; j++) {
			sum += brr[j];
			v2.push_back(sum);
		}
	}

	sort(v1.begin(), v1.end());
	sort(v2.begin(), v2.end());

	long long answer = 0;
	for (int i = 0; i < v1.size(); i++) {
		int low = lower_bound(v2.begin(), v2.end(), t - v1[i]) - v2.begin();
		int top = upper_bound(v2.begin(), v2.end(), t - v1[i]) - v2.begin();
		answer += (top - low);
	}
	cout << answer << '\n';
	return 0;
}