백준 7453 _ Python

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

7453번: 합이 0인 네 정수

문제

---

정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다.

A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오.

 

 

입력

---

첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다.

 

출력

---

합이 0이 되는 쌍의 개수를 출력한다.

 

 

접근법

---

1. 우선 python 에 있는 combination을 써줄려 하다 (너무 많은 수 4^4000 가짓수는 너무 많다..) 반으로 크기를 나눈다음에 포인터로 합이 0이 되는 쌍을 찾아준다.
2. 우선적으로 temp =list(map(int,sys.stdin.readline().split() for _ in range(n)) 으로 list 를 받아준다음 zip(*argument)로 zip 되어 있는 temp를 a,b,c,d 로 나누어준다.
3. 그 다음 for 문을 돌리면서 a[i]+ b[j] 를 X[] 에 저장, c[i]+d[j]를 Y[]에다가 저장 후,
4. collections 의 Counter 을 이용해 합이 0이 되는 놈들을 세어준다.

 

import sys
from collections import Counter

n = int(sys.stdin.readline())
temp = [list(map(int,sys.stdin.readline().split())) for _ in range(n)]

#zip function 에 *을 써주어 unpacking 을 해준다.
a,b,c,d = zip(*temp)
first = []
second = []
# 여기까지가 전처리
for i in range(n):
    for j in range(n):
        first.append(a[i]+b[j])
        second.append(c[i]+d[j])

counter = Counter(second)
ans = 0
for num in first:
    ans += counter[-num]
print(ans)