백준 7453 합이 0인 네 정수

haruponea·2021년 4월 3일
0

BOJ

목록 보기
31/41

문제 링크https://www.acmicpc.net/problem/7453

풀이
모든 경우의 수를 따진다면 O(N^4)만큼 반복해야한다. 하지만 (a, b)의 쌍, (c, d)의 쌍을 만들어 두 경우를 조합한다면 O(N^2)의 복잡도로 풀 수 있다. (a, b)쌍과 (c, d)쌍을 만드는 데 필요한 시간복잡도는 각각 O(N^2)이고 딕셔너리로 찾아보는데 O(1)만큼의 시간이 소요된다. 따라서 O(N^2)의 시간복잡도로 문제를 해결할 수 있다.

Python

import sys
n = int(sys.stdin.readline())
a, b, c, d = [], [], [], []
for _ in range(n):
    n1, n2, n3, n4 = map(int, sys.stdin.readline().split())
    a.append(n1)
    b.append(n2)
    c.append(n3)
    d.append(n4)
dic = {}
cnt = 0
for i in a:
    for j in b:
        if i+j in dic:
            dic[i+j] += 1
        else:
            dic[i+j] = 1
for i in c:
    for j in d:
        if -(i + j) in dic:
            cnt += dic[-(i + j)]
print(cnt)

0개의 댓글