[파이썬/python] 백준 - 1253 좋다

문제

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

---

문제 설명

1. N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 좋다(GOOD)고 한다.
2. N개의 수 중에서 좋은 수의 개수를 출력하라.
   1. 수의 위치가 다르면 값이 같아도 다른 수이다.

 

---

풀이

문제는 단순했다. N개의 숫자중 2개의 숫자를 합했을 때 N개의 숫자에 포함되는 수를 구하면 된다.

문제는 N의 크기다. N은 최대 2000개가 입력된다.

따라서 완전탐색을 통한다면, $N^3 = 10^9$ 정도의 시간이 걸리기 때문에 시간초과가 발생한다.

즉 이를 줄일 수 있는 방법을 고안해야 한다.

 

나는 결과(두 숫자의 합)와 첫 번째 숫자를 택하고 이분탐색을 통해 두 번째 숫자를 탐색했다.

이러한 방식이라면 시간복잡도는 $N^2*logN = 10^7$ 정도의 시간을 가지기 때문에 충분히 문제를 해결할 수 있다.

 

1. N개의 수 중 1개 i를 택한다.
2. 탐색에 사용할 첫 번째 숫자 j를 선택한다.
3. 이분탐색을 통해 두 번째 숫자를 탐색한다.
4. 현재 숫자가 좋다(GOOD)면, 결과를 증가시킨다.

---

코드

import sys
input = sys.stdin.readline

def binary_search(target, arr, skip1, skip2):
    s, e = 0, len(arr) - 1
    while s <= e:
        mid = (s + e) // 2
        if mid == skip1 or mid == skip2:
            if mid < skip1:
                s = mid + 1
            else:
                e = mid - 1
            continue

        if arr[mid] < target:
            s = mid + 1
        elif arr[mid] > target:
            e = mid - 1
        else:
            return True
    return False

N = int(input())
arr = sorted(list(map(int, input().split())))
res = 0

for i in range(N):
    for j in range(N):
        if i == j:
            continue
        target = arr[i] - arr[j]
        if binary_search(target, arr, i, j):
            res += 1
            break
print(res)

---

시간복잡도

• 시간복잡도는 $O(N^2*logN) = O(10^7)$ 이다.