문제 링크

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

문제 설명

• N개의 수 주어짐
• N개의 수 중 서로 다른 수 a, b, c가 있을 때
• a = b + c 일 때 a는 좋은 수
• 좋은 수의 개수 출력

풀이

• 나는 이분 탐색으로 풀었다
  • 정렬 후
  • N개의 수 탐색 (a)
    • 한 번 더 N개의 수를 돌면서 (b)
      • 이분 탐색으로 (a-b)를 찾음 (c)
  • 시간 복잡도 N^2 logN
• 투 포인터로 푸는 방법도 있음
  • 정렬 후
  • s = 0, e = N-1
  • numbers[s] + numbers[e] 가 원하는 값보다 크면
    • e -= 1
  • 작으면
    • s += 1

코드

import sys, bisect

def solution():

    read = sys.stdin.readline
    n = int(read())
    numbers = list(map(int, read().split()))
    numbers.sort()

    count = 0
    for i in range(n):
        if possible(n, numbers, numbers[i], i):
            count += 1

    print(count)

def possible(n, numbers, cn, ci):
    for i in range(n):
        if i == ci:
            continue
        goal = cn - numbers[i]
        j = bisect.bisect_left(numbers, goal)
        while j == i or j == ci:
            j += 1
        if not (0 <= j < n):
            continue
        if goal == numbers[j]:
            return True

solution()