https://www.acmicpc.net/problem/7453
시간 12초, 메모리 1024MB
input :
- n (1 ≤ n ≤ 4000)
- A, B, C, D(정수의 절댓값은 최대 2^28)
output :
- 0이 되는 쌍의 개수를 출력
조건 :
- 크기가 같은 배열 A, B, C, D
- A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수
문제의 첫 접근은 당연히 완전탐색으로 하다가 시간제한이 12초이지만 4000^4 제곱은 불가능 하니까 어떻게 할까 하고 질문들을 찾아보고 있었다.
부분수열의 합 2 문제에서 처럼 배열을 둘로 나눠서 구하길래 아 이거구나 하면서 바로 defauldict(int)로 초기화 해서 문제를 풀었다.
어 근데 이게 왠걸 시간초과가 계속 난다.
문제는 내가 cd의 배열의 모든 경우를 더해준것이 잘못이었다.
0이 아닌 값의 경우에만 더해야 딕셔너리에서 값을 가져오는 시간을 줄이기 때문에 이에대한 조건이 필요하다.
mport sys
from collections import defaultdict
n = int(sys.stdin.readline())
a, b, c, d = [], [], [], []
ab = defaultdict(int)
for i in range(n):
A, B, C, D = map(int, sys.stdin.readline().split())
a.append(A)
b.append(B)
c.append(C)
d.append(D)
for num_a in a:
for num_b in b:
ab[num_a + num_b] += 1
ans = 0
for num_c in c:
for num_d in d:
if ab.get(-(num_c + num_d)):
ans += ab[-(num_c + num_d)]
print(ans)위와 같이 딕셔너리를 이용하든,
배열을 두개로 나눈 다음 이분 탐색을 이용해서 답을 체크 하든 상관 없다.
