[삼성역량테스트] 2143 두 배열의 합

 

풀이일시 : 2021-02-21

 

 

문제 : 

한 배열 A[1], A[2], …, A[n]에 대해서, 부 배열은 A[i], A[i+1], …, A[j-1], A[j] (단, 1 ≤ i ≤ j ≤ n)을 말한다. 이러한 부 배열의 합은 A[i]+…+A[j]를 의미한다. 각 원소가 정수인 두 배열 A[1], …, A[n]과 B[1], …, B[m]이 주어졌을 때, A의 부 배열의 합에 B의 부 배열의 합을 더해서 T가 되는 모든 부 배열 쌍의 개수를 구하는 프로그램을 작성하시오.

예를 들어 A = {1, 3, 1, 2}, B = {1, 3, 2}, T=5인 경우, 부 배열 쌍의 개수는 다음의 7가지 경우가 있다.

 

T(=5) = A[1] + B[1] + B[2]

= A[1] + A[2] + B[1]

= A[2] + B[3]

= A[2] + A[3] + B[1]

= A[3] + B[1] + B[2]

= A[3] + A[4] + B[3]

= A[4] + B[2] 

 

 

 

입력 :

첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다음 줄에 m개의 정수로 B[1], …, B[m]이 주어진다. 각각의 배열 원소는 절댓값이 1,000,000을 넘지 않는 정수이다.

ex)

5

4

1 3 1 2

3

1 3 2

 

 

 

출력 :

첫째 줄에 답을 출력한다. 가능한 경우가 한 가지도 없을 경우에는 0을 출력한다.

ex)

7

 

 

 

풀이 : 

아래의 노트와 같다.

- 모든 부분배열의 합을 구하고 다른 배열에 다시 저장한다.

- pA는 오름차순 pB는 내림차순으로 정렬한다.

- 합이 T이면 pA와 pB 의 포인터가 동시에 증가

- 합이 T보다 작으면 pA의 포인터만 증가 (총합이 증가해야되기 때문)

- 합이 T보다 크면 pB의 포인터만 증가 (총합이 감소해야되기 때문)

 

코드 작성시 주의점 : int의 범위가 넘어가게 되는 경우를 주의하자. long, long long 형으로 정의해주자.

 

 

#define MAX 2000000
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int T, m, n;
int A[1000], B[1000];
vector<long> vA,vB;
long cnt = 0;

long sol() {
	long poa = 0, pob = 0;//시작포인터 지정
	while (!(poa == vA.size() || pob == vB.size())) {
		if (vA[poa] + vB[pob] < T) {
			poa++;
		}
		else if (vA[poa] + vB[pob] == T) {
			long cntA = poa, cntB = pob;
			long ha = poa, hb = pob;
			while (vA[cntA] == vA[poa]) {
				cntA++;
				if (cntA==vA.size())
					break;
			}
			while (vB[cntB] == vB[pob]) {
				cntB++;
				if (cntB==vB.size())
					break;
			}
			poa = cntA;
			pob = cntB;
			cnt += ((poa - ha) * (pob - hb));
		}
		else {
			pob++;
		}
	}
	return cnt;
}

int main() {
	cin >> T >> m;
	int input;
	for (int i = 0; i < m; i++) { //정수갯수
		cin >> A[i];
	}
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> B[i];
	}

	//A로 만들 수 있는 부배열의합을 모두 구해서 vector에 pushback
	//문제이해가 중요 처음엔 연속적이지 않다고 생각했으나 A[i]...A[j]합이 부분합이란걸알게됨
	for (int i = 0; i < m; i++) {
		int num = A[i];
		vA.push_back(num);
		for (int j = i + 1; j < m; j++) {
			num += A[j];
			vA.push_back(num);
		}
	}

	for (int i = 0; i < n; i++) {
		int num = B[i];
		vB.push_back(num);
		for (int j = i + 1; j < n; j++) {
			num += B[j];
			vB.push_back(num);
		}
	}

	sort(vA.begin(), vA.end());
	sort(vB.begin(), vB.end(), greater<int>()); //내림차순으로 정렬한다.
	//pq에서는 greater 가 오름차순

	long res = sol(); //이걸 long 으로 선언안한게 72%에서 끊긴이유
	cout << res << endl;
	return 0;
}