[백준알고리즘] 7453번: 합이 0인 네 정수 -Python

[백준알고리즘] 7453번: 합이 0인 네 정수 -Python

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

7453번: 합이 0인 네 정수

이번 문제를 풀기 전에 1208번 부분수열의 합 2를 먼저 풀어서 그런가 되게 아이디어가 쉽게 떠올랐다.

오히려 이 문제를 먼저 풀었으면 1208번 문제를 질문 게시판을 보지 않고도 풀었을 수도 있을 것 같다.

 

우선 문제를 바라보기만해도 n^4에는 해결할 수 없어보인다. n의 범위가 최대 4000이니 말이다.

 

이 문제는 A배열과 B배열의 합과 C배열과 D배열의 합으로 4개의 배열을 동시에 합치는 것이 아닌 두개씩 합치도록 했다.

A배열과 B배열의 합에서 T라는 값이 있다면 C배열과 D배열의 합에서 -T라는 값이 있으면 0이 될 수 있는 아이디어를 이용했다.

 

시간복잡도는 O(N^2) 정도가 된다.

import sys

n = int(sys.stdin.readline())
alist, blist, clist, dlist = [], [], [], []
for _ in range(n):
    a, b, c, d = map(int, sys.stdin.readline().split())
    alist.append(a); blist.append(b); clist.append(c); dlist.append(d)

ab, cd = {}, {}
for a in alist:
    for b in blist:
        if not ab.get(a+b):
            ab[a+b] = 1
        else:
            ab[a+b] += 1

for c in clist:
    for d in dlist:
        if not cd.get(c+d):
            cd[c+d] = 1
        else:
            cd[c+d] += 1

ans = 0
for _, key in enumerate(ab):
    if cd.get(-key):
        ans += (ab[key] * cd[-key])

print(ans)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다