백준 3151 <합이 0> Python

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

---

이분 탐색 문제입니다.

 

두 개의 수를 고르는 문제였다면 가볍게 투포인터로 풀 수있지만 세 개의 수를 고르는 문제이기에 경우의 수가 기하급수적으로 늘어나 같은 방식으로는 풀 수 없습니다.

 

그렇다면 세 개의 수를 두 개의 수로 줄여주면 됩니다.

제한시간이 4초이기 때문에 최악의 경우 10000 개의 수를 2중 반복하기에도 시간이 넉넉합니다.

그렇다면 두 개의 수를 모두 계산한 뒤 나머지 하나의 수를 찾아주면 됩니다.

 

다만 중복이 발생할 수 있기 때문에 조치를 취해야 합니다.

두 개의 수를 먼저 고른 뒤 나머지 하나의 수를 고를 때, 먼저 고른 두 개의 수 사이에서만 고르게 정한다면 중복은 발생하지 않고 보다 편하게 코드를 짤 수 있습니다.

---

import sys
from bisect import bisect_left, bisect_right

input = sys.stdin.readline


def solution(N, points):
    # 점수 정렬
    points = sorted(points)
    # 개수
    cnt = 0
    # l 포인터
    for l in range(N-2):
        # r 포인터
        for r in range(l+2, N):
            # 양 끝 포인터 합
            sum_points = points[l] + points[r]
            # - 포인터 합 찾기
            left_find = bisect_left(points, -sum_points, l+1, r) 
            right_find = bisect_right(points, -sum_points, l+1, r)

            # 두 포인터의 값이 같으면
            if left_find == right_find:
                # 해당하는 값이 없을 경우
                if left_find >= r or points[left_find] != -sum_points:
                    # 패스
                    continue
                    
                # 해당하는 값이 하나일 경우
                else:
                    cnt += 1
            
            # 두 포인터의 값이 다르면
            else:
                # 해당하는 값이 여러 개
                cnt += right_find - left_find
    
    print(cnt)


# 입력
N = int(input().strip())
points = list(map(int, input().strip().split()))

solution(N, points)