[Python] 7453번 합이 0인 네 정수

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

7453번: 합이 0인 네 정수

---

 

23/12/25

 

 

중간에서 만나기(Meet in the middle) 알고리즘 대표 문제이다.

 

그룹 연습문제를 풀기 위해서 기본 문제를 풀었다.

 

알고리즘 이름이 왜 중간에서 만나기인지 모르겠는데, 아직 문제를 덜 풀어서 그런가 그냥 분할 정복처럼 느껴진다.

 

---

 

문제 접근 방식:

 

 

1. 나이브한 접근 방식

 

나이브하게 저 조건을 만족하도록 $a, b, c, d$쌍을 찾기 위해선 $\mathcal{O}(N^4)$의 시간 복잡도가 소요된다.

 

$N$의 제한은 총 $4,000$까지 였으므로, $2.56 \times 10^{14}$, 즉, $256$조 번의 계산이 필요하다.

 

제한 시간은 $12$초 였기 때문에, 이 접근 방식으로 그대로 구현하면 그냥 시간 초과가 날 것이다.

 

대략 $1$억 번을 계산하는 데에 $1$초 정도가 소요되니까, $30$일 정도 돌려야 답이 나올 것이다...

 

 

2. 시간을 좀 더 줄여 볼 수는 없을까?

 

우리는 시간을 줄이기 위해 퀵 소트에서 사용되는 방법 처럼 그룹을 묶어서 볼 것이다.

 

즉, AB와 CD를 묶어서 보자.

 

그룹 A와 그룹 B의 합 배열과, 그룹 C와 그룹 D의 합 배열을 생성하는 데에는 각각 $\mathcal{O}(N^2)$의 시간 복잡도가 소요된다.

 

만약 여기서 저 두 합 배열을 이용해서 A, B, C, D의 합 배열을 만든다면 당연히 $\mathcal{O}(N^4)$의 시간 복잡도가 소요될 것이다.

 

편의 상 그룹 A와 그룹 B의 합 배열을 AB배열이라고 부르고 그룹 C와 그룹 D의 합 배열을 CD배열이라고 부르자.

 

CD배열이 "정렬"되어 있다고 하면, 우리는 이분 탐색이나 투 포인터 적 기법을 활용해서 시간 복잡도를 로그로 줄일 수 있을 것이다.

 

CD배열을 정렬해보자.

 

우리는 이후 AB배열의 한 원소($A[i] + B[j]$)마다, $A[a] + B[b] + C[c] + D[d] = 0$을 만족하는 원소 $C[i] + D[j]$를 정렬된 CD배열에서 찾을 것이다.

 

배열이 정렬되어 있기 때문에, 투 포인터로 찾든, 이분 탐색을 활용하여 찾든, 찾아주면 된다.

 

이때의 시간은 로그 복잡도가 소요되기 때문에, 이분 탐색을 활용해서 찾는다면 $\mathcal{O}(N^2\mathrm{log}N)$의 시간 복잡도가 소요된다.

 

나의 경우는 초기 접근 방식이 bisect모듈을 활용한 이분 탐색이었으나, 시간 초과를 받아서 투 포인터로 접근했다.

 

투 포인터로 접근 한다면 AB배열도 정렬해줘야 한다.

 

AB배열은 원래대로 정렬하고, CD배열은 거꾸로 정렬했다고 하면, AB배열은 음수, CD배열은 양수 먼저 배열이 되어있을 것이다.

 

두 배열의 첫 번째 원소끼리 더해서 양수라면, AB배열의 원소보다 CD배열의 원소가 더 크다고 할 수 있으므로, CD배열의 포인터를 움직여주면 된다.

 

마찬가지로, 음수라면 AB배열의 포인터를 움직여주면 된다.

 

두 배열의 크기의 합은 $2N^2$의 크기를 가지므로, 투 포인터를 사용한다면 최악의 경우라도 저 시간복잡도를 소요하여 문제를 해결할 수 있다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 7453번 합이 0인 네 정수
# 분할 정복, 중간에서 만나기
'''
접근 방법:
그냥 무지성 구현하면 O(n^4)이라서 시간 초과가 난다.
그러면 어떻게 해야 할까?
AB와 CD를 묶어서 보자.
각각의 합을 구하는 것은 O(n^2)의 시간 복잡도가 소요된다.
이후 그에 걸맞는 합을 찾는 것은 이분탐색으로 가능하므로, O(n^2*logn)으로 가능하다.
시간초과나서 투포인터로 가봄
'''
import sys
input = sys.stdin.readline
from bisect import bisect_left, bisect_right

N = int(input())
A, B, C, D = [0 for _ in range(N)], [0 for _ in range(N)], [0 for _ in range(N)], [0 for _ in range(N)]
for i in range(N):
    a, b, c, d = map(int, input().split())
    A[i], B[i], C[i], D[i] = a, b, c, d
AB, CD = [0 for _ in range(N*N)], [0 for _ in range(N*N)]
for i in range(N):
    for j in range(N):
        AB[i*N+j] = A[i]+B[j]
        CD[i*N+j] = C[i]+D[j]
AB.sort()
CD.sort(reverse = True)
total = 0
abp, cdp = 0, 0
ab_count, cd_count = 0, 0
while abp < N*N and cdp < N*N:
    if AB[abp] + CD[cdp] > 0:
        cdp += 1
    elif AB[abp] + CD[cdp] < 0:
        abp += 1
    else:
        ab_count += 1
        cd_count += 1
        while True:
            abp += 1
            if abp == N*N or AB[abp] != AB[abp-1]:
                break
            ab_count += 1
        while True:
            cdp += 1
            if cdp == N*N or CD[cdp] != CD[cdp-1]:
                break
            cd_count += 1
        total += ab_count*cd_count
        ab_count, cd_count = 0, 0
print(total)