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

 

www.acmicpc.net/problem/2143

2143번: 두 배열의 합

[문제 풀이]

메모제이션을 이용하여 문제를 풀었습니다.

 

이 문제는 입력된 A, B 배열의 연속 된 부분 배열의 합 중에 두 부분 배열의 합이 T와 같은 부분 배열의 개수를 구하는 문제였습니다. 

문제의 로직은 A, B의 모든 합을 저장하여 정렬한 후 합의 경계를 찾아 경우의 수를 찾는 방식으로 구현하였습니다.

 

코드 설명

• A 배열에 값을 저장하고, A에서 나올 수 있는 모든 부분 합을 저장한다. 
• B 배열에 값을 저장하고, B에서 나올 수 있는 모든 부분 합을 저장한다.
• A 배열의 모든 값을 반복문을 통해서 돌면서 T - A_Sum[i]의 값이 B_Sum[i]가 될 수 있는 최대, 최소 경계를 구해서 경우의 수를 계산해준다.

lower_boud, upper_bound에 대한 개념은 아래에 링크에 정리되어있습니다.

 

steady-life.tistory.com/74

(C++ STL) lower_bound, upper_bound

[코드]

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

using namespace std;

long long T;
int N, M;

int A[1001], B[1001];
vector<int> A_Sum, B_Sum;


int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> T >> N;

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

	int sum = 0;

	for (int i = 0; i < N; i++) {

		sum = A[i];
		A_Sum.push_back(sum);

		for (int j = i + 1; j < N; j++) {
			sum += A[j];

			A_Sum.push_back(sum);
		}


	}

	cin >> M;

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

	for (int i = 0; i < M; i++) {

		sum = B[i];
		B_Sum.push_back(sum);

		for (int j = i + 1; j < M; j++) {
			sum += B[j];

			B_Sum.push_back(sum);
		}

	}

	sort(A_Sum.begin(), A_Sum.end());
	sort(B_Sum.begin(), B_Sum.end());

	long long answer = 0;

	for (auto item : A_Sum) {

		int temp = T - item;

		auto lower = lower_bound(B_Sum.begin(), B_Sum.end(), temp);
		auto upper = upper_bound(B_Sum.begin(), B_Sum.end(), temp);

		answer += (upper - lower);

	}

	cout << answer << endl;

	return 0;

}