[G2] 백준 7453 - 합이 0인 네 정수 (Python3)

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

---

완전탐색( O(n^4) )으로 모든 경우의 수(조합)을 따져서 풀면 시간 안에 절대 해결할 수 없다.

4,000 × 4,000 × 4,000 × 4,000 = 256,000,000,000,000 (256조 번 연산)

따라서 더 효율적인 방법이 필요하다.

💡 아이디어

A[a] + B[b] + C[c] + D[d] = 0

을 만족하는 (a,b,c,d) 순서쌍의 개수를 구하는 문제이다.위 식을( A[a] + B[b] ) + ( C[c] + D[d] ) = 0 으로 고쳐 써도 전혀 문제 없다. AB: 모든 A[i]+B[j] 조합을 저장한 배열 CD: 모든 C[k]+D[l] 조합을 저장한 배열그래서 AB[i]+CD[j]=0 인 경우의 개수를 세면 이 문제가 원하는 답을 구할 수 있다.

🚫주의

AB와 CD를 구했다고 무턱대고 2중첩 반복문으로 모든 AB와 모든 CD의 합을 따지면 마찬가지로 O(n^4)로 256조 번의 연산을 해야한다.

---

 

 

 

AB[i] + CD[j] = 0 일때, AB[i] = -CD[j] 이다.

즉, (-1 * AB[i]) 값이 CD에 있는지 확인만 하면 된다.

Python3에서는 in 연산자가 (-1 * AB[i]) 존재 여부를 쉽게 따질 수 있는 연산자일 것이다.

하지만 배열에서 in 을 사용하면 O(n)인 반면, 딕셔너리나 집합에서 in은 O(1)이다.

 

AB에는 같은 수가 중복해서 존재할 수도 있으므로, 딕셔너리를 선택하는 것이 좋아보였다. 그래서 dict_ab를 만들어서 AB의 모든 원소(key)와 개수(value)를 넣었다. 모든 원소에는 (-1)을 곱한 상태다.

 

반복문으로 CD의 모든 원소를 dict_ab에 존재하는지 따지고, 존재한다면 개수만큼 answer에 더해준다.

---

🧾코드

#7453 합이 0인 네 정수
n = int(input())

A, B, C, D = [], [], [], []
for _ in range(n):
    a, b, c, d = map(int, input().split())
    A += [a]
    B += [b]
    C += [c]
    D += [d]

# 모든 A[a]+B[b] 합을 담을 AB 배열과 CD배열
AB = []
CD = []

for a in A:
    for b in B:
        AB.append(a + b)
for c in C:
    for d in D:
        CD.append(c + d)

# AB[i] + CD[j] = 0 은
# AB[i] = -CD[j] 이므로
# CD에 AB[i] * -1 이 있는지 확인만 하면 된다.
# 딕셔너리는 in 연산이 O(1) 인 점에서 AB[i] * -1 접근속도에 장점이 있다. 그래서 딕셔너리를 사용한다.
dict_ab = {}
for key in AB:
    key *= -1
    if key not in dict_ab:
        dict_ab[key] = 1
    else:
        dict_ab[key] += 1

answer = 0
for n in CD:
    if n in dict_ab:
        answer += dict_ab[n]
print(answer)