8017 : 합이 0인 4개의 값
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
각각 $N$개의 정수를 포함하는 4개의 리스트 $A, B, C, D$가 주어집니다.
$A[i] + B[j] + C[k] + D[l] = 0$이 되는 네 인덱스의 순서쌍 $(i, j, k, l)$의 개수를 구하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N \le 1,000$
• 각 리스트 원소들의 절댓값은 $2^{28}$ 이하입니다.
$A[i] + B[j] + C[k] + D[l] = 0$이 되는 네 인덱스의 순서쌍 $(i, j, k, l)$의 개수를 구하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N \le 1,000$
• 각 리스트 원소들의 절댓값은 $2^{28}$ 이하입니다.
입력 설명
첫째 줄에 각 리스트의 크기 $N$이 주어집니다.
둘째 줄부터 $N$개의 줄에 걸쳐 각 줄에 네 정수 $A[i], B[i], C[i], D[i]$가 공백으로 구분되어 주어집니다.
둘째 줄부터 $N$개의 줄에 걸쳐 각 줄에 네 정수 $A[i], B[i], C[i], D[i]$가 공백으로 구분되어 주어집니다.
출력 설명
합이 0이 되는 네 인덱스 쌍의 총 개수를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
6
-29 79 77 -16
-25 -52 92 -26
-20 27 -20 -9
-12 1 -46 -8
-12 -22 -91 -7
-6 26 -28 -17
출력 예시
COPY
복사되었습니다!
복사되었습니다!
5도움
절반으로 나누어 탐색(Meet-in-the-middle) 기법을 사용합니다.
1. $A$와 $B$의 모든 가능한 합 $A[i] + B[j]$ ($N^2$개)의 빈도수를 해시 맵(또는 정렬 배열)에 기록합니다.
2. $C$와 $D$의 모든 가능한 합 $-(C[k] + D[l])$을 구하면서 해시 맵에 저장된 빈도수를 정답에 누적하여 $O(N^2)$ 시간에 해결합니다.
1. $A$와 $B$의 모든 가능한 합 $A[i] + B[j]$ ($N^2$개)의 빈도수를 해시 맵(또는 정렬 배열)에 기록합니다.
2. $C$와 $D$의 모든 가능한 합 $-(C[k] + D[l])$을 구하면서 해시 맵에 저장된 빈도수를 정답에 누적하여 $O(N^2)$ 시간에 해결합니다.