백준 7453번 합이 0인 네 정수

< 백준 7453번 합이 0인 네 정수 - 마포 코딩박 >

사용한 알고리즘: 투포인터


 크기가 N 인 네 배열 A, B, C, D 가 주어지고, 각 배열에서 원소 한개씩 더해 0이 되는 쌍의 수를 구하는 문제였습니다.

문제풀이는 다음과 같습니다.
(1) (코드 13~22)
 A,B 의 가능한 모든 합과 C,D 의 가능한 모든 합을 따로 구해 크기순으로 정렬합니다.

(2) (코드 24~45)
  A,B합은 큰 것부터, C,D합은 작은것 부터 보며, A,B합 과 C,D합 을 더해 0 이 될 수 있는 경우를 구합니다.
 이를 구현할 때 투포인터를 써서 구현했습니다.

	#include <bits/stdc++.h>
	using namespace std;
	const int MAX = 4000;
	// 투포인터
	int N, ans, arr[4][MAX+1];
	vector<int> ab, cd;
	int main(){ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; ++i)
	cin >> arr[0][i] >> arr[1][i] >> arr[2][i] >> arr[3][i];
	// A, B 가능한 모든 합 저장
	for (int i = 0; i < N; ++i)
	for (int j = 0; j < N; ++j)
	ab.push_back(arr[0][i]+arr[1][j]);
	// C, D 가능한 모든 합 저장
	for (int i = 0; i < N; ++i)
	for (int j = 0; j < N; ++j)
	cd.push_back(arr[2][i]+arr[3][j]);
	sort(ab.begin(),ab.end());
	sort(cd.begin(),cd.end());
	long long res = 0;
	int lo = 0, hi = N*N - 1;
	// ab의 큰값부터, cd의 작은값부터 본다.
	while(hi >= 0 && lo < N * N){
	// 합이 0 인 경우
	if(-ab[hi] == cd[lo]){
	// ao: 해당 ab 개수, at: 해당 cd 개수
	int ao = 0, at = 0;
	int temp = cd[lo];
	while ((-ab[hi] == temp) && hi >= 0)
	ao++, hi--;
	while (cd[lo]==temp && lo<N*N)
	at++, lo++;
	// 구하고자 하는건 모든 '쌍의 수'이다.
	res += (long long)ao*at;
	}
	//절대값 비교
	else if (-ab[hi] < cd[lo])
	hi--;
	else
	lo++;
	}
	cout << res << '\n';
	return 0;
	}

view raw BOJ 7453.cpp hosted with ❤ by GitHub