백준 No.7453 [합이 0인 네 정수]

Baekjoon Online Judge No.7453 [합이 0인 네 정수]

---

  문제 

7453번: 합이 0인 네 정수 (acmicpc.net)

7453번: 합이 0인 네 정수

---

  설명 

  투 포인터 알고리즘을 활용하여 풀었다. 투 포인터를 하기 이전 투 포인터를 할 수 있는 상태를 만들어야 한다. 

 

 

  위와 같이 4개의 배열이 주어졌다고 할 때, 결국 네 배열의 원소의 합이 0인 경우가 몇 번 있는지를 찾는 것 이므로, 각각의 배열들은 다른 배열과 무조건 한 번씩은 더해지는 작업을 거치게 된다. 즉, 두 배열의 원소들을 합 한 모든 경우의 값들을 가지고 있는 배열을 새로 구상할 수 있다. 아래에서 A, B 배열을 합친 원소들의 값들의 모음인 AB 배열, C, D 배열을 합친 원소들의 값들의 모음인 CD배열을 나타내보았다.

 

 

  A, B, C, D 배열의 원소들의 합이 0이 되는 경우는 위 AB, CD  두 배열의 원소의 합이 0이 되는 경우와 동일하다. 아래처럼 이 두 배열을 오름차순으로 정렬한 수 투 포인터 알고리즘을 통해 합이 0이 되는 경우의 개수를 체크할 수 있다.

 

 

투 포인터 알고리즘 링크 :

2021.07.20 - [Algorithm (C++ based)/Algorithm 이론] - 투 포인터 알고리즘 (Two pointer Algorithm)

투 포인터 알고리즘 (Two pointer Algorithm)

  고찰 Note

1. 투 포인터에서, left, right pointer 를 이동을 시킬 때 만약 투 포인터 알고리즘에 적용된 배열이 같은 값을 가지는 원소가 있다면 그 점을 감안하여 코드를 구현해야 한다. 나는 upper_bound algorithm 을 사용하여 이 점을 파악하고, 그에 맞게 answer 의 값을 늘려주었다.
2. 이전에도 문제가 되었던 부분인데, 아무리 값을 대입받는 부분을 long long 으로 선언을 했어도 결국 그 값을 계산하는 연산 과정에서 int type 을 가지는 값 끼리 계산을 할 때 overflow 가 발생할 수 있다. 조심해야한다.

 

 

---

  Code 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#define MAX 4000

using namespace std;
typedef unsigned long long ull;

int A[MAX], B[MAX], C[MAX], D[MAX];
vector<int> AB;
vector<int> CD;
int n;

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

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> A[i] >> B[i] >> C[i] >> D[i];
	} 

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			AB.push_back(A[i] + B[j]);
			CD.push_back(C[i] + D[j]);
		}

	sort(AB.begin(), AB.end());
	sort(CD.begin(), CD.end());

	int left = 0, right = CD.size() - 1;
	ull answer = 0;
	int sum = 0;

	while (left < AB.size() && 0 <= right) {
		sum = AB[left] + CD[right];

		if (sum < 0) left++;
		else if (0 < sum) right--;
		else {
			int nxtLeft = upper_bound(AB.begin(), AB.end(), AB[left]) - AB.begin();
			int nxtRight = lower_bound(CD.begin(), CD.end(), CD[right]) - CD.begin() - 1;

			answer += (ull(nxtLeft) - ull(left)) * (ull(right) - ull(nxtRight));
			left = nxtLeft;
			right = nxtRight;
		}
	}

	cout << answer;
}