[알고리즘] 합이 0인 네 정수 백준 7453 python

문제 바로가기

풀이

완전탐색을 돌릴 경우 O(n^4)가 걸려서 풀리지 않을 게 보입니다.
배열 4개의 원소의 합이 0이 되도록 조합하는 문제이므로 두개의 배열의 원소의 합과 다른 두개의 배열의 원소의 합을 저장하고 부호를 비교하는 방법으로 진행하면 될 것 같습니다.
또한 배열에 저장해서 값이 있는지 찾는 것이 아닌 dictionary에 해당 값이 나오면 +1을 해주면 찾을 때 훨씬 빠르게 찾을 수 있습니다.

1. A와 B 배열의 원소들의 합을 모두 AB라는 딕셔너리에 (값, 나온 횟수)로 저장한다.
2. C와 D 배열의 원소들의 합을 완전탐색하면서 AB에 -(해당하는 값)이 있는지 검사한다.
3. 해당하는 값이 있는 경우 AB[-해당하는 값]의 값만큼 final에 더해준다.

지금은 dictionary를 이용해서 편하게 풀었지만, 이분 탐색을 이용해서 AB, CD라는 리스트를 만들고,
-AB에 있는 값이 CD에 있는지 이분탐색으로 풀어도 가능할 것 같습니다.

N = int(input())

final = 0
A = []
B = []
C = []
D = []
AB = dict()
for _ in range(N):
    a,b,c,d = map(int, input().split(" "))
    A.append(a)
    B.append(b)
    C.append(c)
    D.append(d)

for i in range(N):
    for j in range(N):
        temp = A[i] + B[j]
        if temp in AB:
            AB[temp] += 1
        else:
            AB[temp] = 1
for i in range(N):
    for j in range(N):
        temp = -(C[i] + D[j])
        if temp in AB :
            final += AB[temp]

print(final)