백준 7453 - 합이 0인 네 정수 (파이썬)

난이도

골드 2

 

유형

중간에서 만나기

 

해결

브루트 포스로 해결하기에는 4천의 4제곱이라는 터무니 없는 숫자라서 불가능하다. 중간에서 만나기 알고리즘을 활용하여 획기적으로 시간을 줄여줄 수 있다. 총 4개의 숫자가 여러 줄에 걸쳐서 존재한다. 앞에 2개를 조합하는 경우를 키 값으로 그리고 그 경우의 수를 밸류로 갖는 딕셔너리를 만들어준 뒤 뒤의 2개를 조합하여 만든 숫자에 -1을 곱한 수를 키 값으로 활용해주면 된다. 이유는 ( A+B ) - ( C + D ) 이미 저장해놓은 임의의 A+B이 값이 임의의 C+D와 더해서 0이 되려면 C+D=-(A+B)이여야 하므로이다. 앞 2개 뒤 2개만 for문으로 돌렸으니 4중 for문보다는 훨씬 빠르게 답을 구할 수 있다.

 

defaultdict를 사용시 에러가 발생한다.

게시판에서 해당 글을 주울 수 있었다. https://stackoverflow.com/questions/19629682/ordereddict-vs-defaultdict-vs-dict

OrderedDict vs defaultdict vs dict

코드

from sys import stdin
from collections import defaultdict
input=stdin.readline

n=int(input())
arr=[]
cnt=0
for i in range(n):
    arr.append(list(map(int,input().split())))

two={}
for i in range(n):
    for j in range(n):
        try:
            two[arr[i][0]+arr[j][1]]+=1
        except:
            two[arr[i][0]+arr[j][1]]=1

for i in range(n):
    for j in range(n):
        try:
            cnt+=two[-(arr[i][2]+arr[j][3])]
        except:
            pass

print(cnt)

좋은 / 비슷한 문제