문제:
정수로 이루어진 크기가 같은 배열 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에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 2^28이다.
출력:
합이 0이 되는 쌍의 개수를 출력한다
풀이방법:
***Pypy3으로 통과한 문제입니다.***
이 문제를 그냥 완전탐색으로 풀면 O(N^4)가 되고, N은 최대 4000까지 주어지므로 시간초과가 발생할 것이다. 따라서 4개의 배열을 두개씩 묶어서 O(N^2)으로 줄이도록 한다.
A와 B의 가능한 합의 경우의 수를 담고 있는 one을 해싱 방법으로 딕셔너리 형태로 저장한다. 포함되는 정수가 중복이 없다는 조건이 없기 때문에, 해당하는 키가 여러개 존재할 수 있으므로 key,value = (두 정수의 합, 나타나는 횟수)와 같이 딕셔너리 형태로 저장한다.
C와 D의 가능한 합의 경우의 수를 구하면서 이 합의 마이너스 부호를 취한 것이 one 딕셔너리에 있다면 합이 0이 되는 경우이므로 value 값을 answer에 더하도록 한다.
**[21.01.17 수정]현재 재채점으로 인해 아래 코드도 통과하지 못합니다.**
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
import sys
N = int(sys.stdin.readline())
A,B,C,D = [0]*N,[0]*N,[0]*N,[0]*N
for i in range(N):
A[i],B[i],C[i],D[i] = map(int,sys.stdin.readline().split())
one = dict()
for a in A:
for b in B:
if not one.get(a+b):
one[a+b]=1
else:
one[a+b]+=1
answer = 0
for c in C:
for d in D:
two = -(c+d)
if one.get(two):
answer +=one.get(two)
print(answer)
|
cs |
문제링크:
7453번: 합이 0인 네 정수
첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다.
www.acmicpc.net
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]11723. 집합 (0) | 2020.12.24 |
|---|---|
| [BOJ]1527. 금민수의 개수 (0) | 2020.12.22 |
| [BOJ]2294. 동전 2 (0) | 2020.12.08 |
| [BOJ]11060. 점프 점프 (0) | 2020.12.03 |
| [BOJ]10835. 카드게임 (0) | 2020.12.01 |