백준 2143 - 두 배열의 합(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2143

2143번: 두 배열의 합

upper, lower_bound를 사용하는 문제였습니다.

배열 A와 B 중, 하나 이상을 선택해 합이 T를 만드는 부분 수열의 갯수를 구하는 문제입니다.

 

N과 M값이 1,000이기에 이중 for문을 통해서 모든 부분 수열의 합을 구합니다.

 

A 부분 수열과 B 부분 수열의 합을 구하는 것이기에, 

배열 하나를 정해서 T에서 값을 뺍니다. 

그 후에, lower_bound, upper_bound를 구한 뒤, 두 값의 차를 더해주면 됩니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>
#include <stack>
#include <map>
#define LL long long
#define pp pair<int, int>
#define F first
#define S second

using namespace std;

int N, M, T;
int A[1001], B[1001];
vector<int> sum_A, sum_B;

void solve(){
    LL ans = 0;
    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);
        }
    }
    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);
        }
    }
    sort(sum_A.begin(), sum_A.end());
    sort(sum_B.begin(), sum_B.end());
    for(int i = 0; i < sum_A.size(); i++){
        int st = lower_bound(sum_B.begin(), sum_B.end(), T-sum_A[i]) - sum_B.begin();
        int end = upper_bound(sum_B.begin(), sum_B.end(), T-sum_A[i]) - sum_B.begin();
        ans += (end - st);
    }
    cout << ans;
}

int main() {
    cin.tie(0);
	cout.tie(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];
	solve();
	return 0;
}

 

질문 및 조언은 댓글을 남겨주세요