합이 0인 네 정수
문제
정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다.
A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다.
출력
합이 0이 되는 쌍의 개수를 출력한다.
예제 입력
6
-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
-36 30 -75 -46
26 -38 -10 62
-32 -54 -6 45
예제 출력
5
풀이
이전에 풀었던 2470번 두 용액 문제와 비슷하다고 생각했다. 두 용액 문제는 주어진 수들 중 두 수의 합이 0에 가까운 수의 순서쌍을 찾는 문제였다. 2470번을 풀때는 정렬 후 처음과 끝을 가리키는 두 포인터를 설정하고 두 수의 합에 따라 포인터를 이동하는 방식으로 문제를 풀었었다.
근데 이번 문제는 수가 총 4가지로 분류되어 있어서 두 포인터를 어떻게 설정할지가 문제였다.
두 포인터를 적용하기 위해서 4가지로 분류된 수를 2개씩 묶어서 2가지로 만들었다.
(A B C D 배열이 있으면 A B로 만들 수 있는 순서쌍의 합과 C D로 만들 수 있는 순서쌍의 합)
함수 자료형을 int로 해서 몇분동안 삽질했다..
#include <iostream>
#include <algorithm>
using namespace std;
int **input, n;
long long * combine1, * combine2;
bool compare(long long a, long long b)
{
if(a > b)return true;
else return false;
}
void init()
{
cin >> n;
input = new int *[4];
for(int i = 0; i < 4; i++)input[i] = new int[n];
for(int i = 0; i < n; i++)cin >> input[0][i] >> input[1][i] >> input[2][i] >> input[3][i];
combine1 = new long long [n*n];
combine2 = new long long [n*n];
}
void combine()
{
int index = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++, index++){
combine1[index] = input[0][i] + input[1][j];
combine2[index] = input[2][i] + input[3][j];
}
}
sort(combine1, combine1+(n*n));
sort(combine2, combine2+(n*n), compare);
}
long long solve()
{
long long cnt = 0;
int ptr1 = 0, ptr2 = 0;
while(ptr1 != n*n && ptr2 != n*n)
{
long long sum = combine1[ptr1] + combine2[ptr2];
if(sum == 0)
{
int temp1 = combine1[ptr1];
int temp2 = combine2[ptr2];
long long cnt1 = 0, cnt2 = 0;
while(ptr1 != n*n && combine1[ptr1] == temp1)ptr1++, cnt1++;
while(ptr2 != n*n && combine2[ptr2] == temp2)ptr2++, cnt2++;
cnt += cnt1 * cnt2;
}
else
{
if(sum > 0)ptr2++;
else ptr1++;
}
}
return cnt;
}
int main()
{
init();
combine();
cout << solve();
}
'알고리듬 > 문제' 카테고리의 다른 글
[baekjoon] 23354 (0) | 2023.04.24 |
---|---|
[baekjoon] 7569 (0) | 2023.04.17 |
[baekjoon] 1194 (0) | 2023.04.10 |
[baekjoon] 12100 (0) | 2023.03.23 |
[baekjoon] 14502 (0) | 2023.03.21 |