BOJ 7453 합이 0인 네 정수

사용한 알고리즘

투 포인터

알고리즘 설명

4줄에 N개의 요소를 배열에 저장한다.
1번째 줄과 2번째 줄끼리 더하여 N * N개의 두 수의 합을 만들고 3번째 줄과 4번째 줄 또한 똑같은 작업을 진행한다.
두 수의 합을 저장한 배열을 모두 오름차순으로 정렬한다.
각 두 줄을 A, B 배열이라고 하면 A배열 요소와 B배열 요소를 더하면 4개의 합을 표현할 수 있다.
처음에 A 배열의 첫번째 요소를 하나의 포인터가 가리키고, B 배열의 마지막 요소를 또 하나의 포인터가 가리킨다.
A 배열의 포인터를 증가시키면 4개의 합 값은 증가하고, B 배열 포인터를 줄이게 되면 4개의 합이 감소한다.
이와 같은 두 가지의 방향성으로 값이 0보다 작은 경우 A 배열 포인터를 증가시키고, 0보다 큰 경우는 B 배열 포인터를 줄이고, 같은 경우는 A 배열 포인터는 증가, B 배열 포인터는 감소 시킨다.
4개의 합이 0인 경우 개수를 센다.
while 문을 이용하여 같은 값을 가지는 개수를 세서 처리한다.

풀이

// baekjoon 7453_2 yechan Two-pointer
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_N=4000;
typedef long long ll;

int N;
ll ret=0, board[4][4000], twoSum0[16000001], twoSum1[16000001];
ll Acnt=0, Bcnt=0, Aval, Bval, Tval;

int main() {
	scanf("%d", &N);
	int NN = N*N;
	for (int i=0; i<N; i++)
		for (int j=0; j<4; j++)
			scanf("%lld", &board[j][i]);

// 두개의 합을 twoSum0와 twoSum1 배열에 저장한다.
	for (int i=0, z=0; i<N; i++) {
		for (int j=0; j<N; j++, z++) {
			twoSum0[z] = board[0][i] + board[1][j];
			twoSum1[z] = board[2][i] + board[3][j];
		}
	}

	sort(twoSum0, twoSum0+NN);
	sort(twoSum1, twoSum1+NN);

// 두 개의 포인터인 Apos와 Bpos를 생성한다.
	int Apos = 0, Bpos = NN-1;
	while ((Apos < NN) && (Bpos >= 0)) {
		Aval = twoSum0[Apos];
		Bval = twoSum1[Bpos];
		Tval = Aval + Bval;
// 현재 포인터 지점의 개수가 아직 새지 않은 경우 Acnt가 0임
		if (Acnt == 0) {
// 현재 포인터의 개수 새기
			while ((Apos < NN) && (Aval == twoSum0[Apos])) Apos++, Acnt++;
			Apos--;
		}
		if (Bcnt == 0) {
			while ((Bpos >= 0) && (Bval == twoSum1[Bpos])) Bpos--, Bcnt++;
			Bpos++;
		}
// 4개의 합 값이 0과 같은 경우
		if (Tval == 0) {
			Apos++, Bpos--, ret += Acnt*Bcnt;
			Acnt = Bcnt = 0;
		}
// 0보다 큰 경우
		else if (Tval > 0) Bcnt=0, Bpos--;
// 0보다 작은 경우
		else Acnt=0, Apos++;
	}
	printf("%lld\n", ret);
	return 0;
}