[BOJ] 7453 / 합이 0인 네 정수 / Python 파이썬

[BOJ] 7453 / 합이 0인 네 정수 / Python 파이썬

[BOJ] 7453 / 합이 0인 네 정수 / Python 파이썬

https://www.acmicpc.net/problem/7453

7453번: 합이 0인 네 정수

 

 

풀이

A, B, C, D 네 배열 각각의 원소 하나씩을 뽑아 그 합이 0이 되는 쌍의 조합의 개수를 구하는 문제이다.

 

A, B, C, D 네 쌍을 한번에 완전탐색으로 진행하게 되면 최대 4000**4 가 되기 때문에

A 와 B 의 원소 조합으로 만들수 있는 경우를 구한뒤, C 와 D 의 조합을 구하여 해결하였다.

 

N = int(input())

A = [0] * N
B = [0] * N
C = [0] * N
D = [0] * N

for i in range(N):
    A[i], B[i], C[i], D[i] = map(int, input().split())

add_A_B = {}
for a in A:
    for b in B:
        if a+b not in add_A_B:
            add_A_B[a+b] = 1
        else:
            add_A_B[a+b] += 1

res = 0

for c in C:
    for d in D:
        if -(c+d) in add_A_B:
            res += add_A_B[-(c+d)]

print(res)