문제:

정수로 이루어진 크기가 같은 배열 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
= 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

문제링크:

www.acmicpc.net/problem/7453

 

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

+ Recent posts