백준 7453번 - 합이 0인 네 정수

출처 : 7453번: 합이 0인 네 정수 (acmicpc.net)

7453번: 합이 0인 네 정수

 

---

 

합이 0인 네 정수 성공출처다국어분류

한국어   

시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율

12 초 (추가 시간 없음)

1024 MB

19912

4779

2650

22.488%

문제

정수로 이루어진 크기가 같은 배열 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 - 문제 풀이 아이디어

 

---

 

[ 코드 ]

 

import sys
from itertools import combinations

n = int(input())
A, B, C, D = [], [], [], []
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)

ab = []
cd = []
for i in range(n):
    for j in range(n):
        ab.append(A[i] + B[j])
        cd.append(C[i] + D[j])

ab.sort()
cd.sort()

# print(ab, cd)

ans = 0
left = 0
right = len(cd) - 1
while left < len(ab) and right >= 0:
    if ab[left] + cd[right] > 0:
        right -= 1
    elif ab[left] + cd[right] < 0:
        left += 1
    else:
        # 같은 숫자가 나왔을 때 한 쪽만 옮겨서 같은 수가 나올 확률도 있으니 조사해 보는 것
        # print(ab[left], cd[right])
        a_size = 1
        b_size = 1
        while left < len(ab) - 1 and ab[left + 1] == ab[left]:
            left += 1
            a_size += 1
        while right > 0 and cd[right - 1] == cd[right]:
            right -= 1
            b_size += 1
        ans += (a_size * b_size)
        left += 1
        right -= 1

print(ans)

 

---

후기

 

이전 포스팅과 구현 모습은 다르지만

기본적인 원리는 같다.