합이 0인 네 정수

면접 대비

시간 제한12초메모리 제한1024 MB

요약

크기가 n인 네 배열 A, B, C, D에서 A[a] + B[b] + C[c] + D[d] = 0을 만족하는 인덱스 튜플 (a, b, c, d)의 개수를 센다.

난이도: 보통10점 중 6점
유형: 해시맵, 정렬, 투 포인터, 배열
정답자: 아직 제출이 없습니다

문제

크기가 같은 정수 배열 $A$ , $B$ , $C$ , $D$ 가 주어진다.

$A[a] + B[b] + C[c] + D[d] = 0$ 을 만족하는 순서쌍 $(a, b, c, d)$ 의 개수를 구하는 프로그램을 작성하시오. 여기서 $a$ , $b$ , $c$ , $d$ 는 각각 $0$ 부터 $n-1$ 까지의 인덱스이며, 네 배열에서 원소를 하나씩 독립적으로 고른다.

입력

첫째 줄에 배열의 크기 $n$ $(1 \le n \le 4000)$ 이 주어진다. 다음 $n$ 개의 줄에는 각 줄마다 $A$ , $B$ , $C$ , $D$ 에 들어갈 정수가 공백으로 구분되어 순서대로 주어진다. 즉 $i$ 번째 줄의 네 정수는 차례로 $A[i]$ , $B[i]$ , $C[i]$ , $D[i]$ 이다. 배열에 들어 있는 정수의 절댓값은 최대 $2^{28}$ 이다.

출력

합이 $0$ 이 되는 순서쌍 $(a, b, c, d)$ 의 개수를 출력한다.

예제4

예제 1

입력

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

예상 출력

예제 2
입력
```
1
0 0 0 0
```
예상 출력
```
1
```
예제 3
입력
```
1
1 1 1 1
```
예상 출력
```
0
```
예제 4
입력
```
2
1 1 1 1
-1 -1 -1 -1
```
예상 출력
```
6
```