[99클럽/파이썬 챌린저/10일차] 좋다

백준 1253번 좋다 G4

 

문제
N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.
N개의 수가 주어지면 그중에서 좋은 수의 개수는 몇 개인지 출력하라.수의 위치가 다르면 값이 같아도 다른 수이다.

입력
첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000)
두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)

출력
좋은 수의 개수를 첫 번째 줄에 출력한다.

 

 

자료구조, 정렬, 이분 탐색, 두 포인터

 

N이 매우 작아서 O(N^2) 풀이로도 풀리는 문제이다.

수를 오름차순으로 정렬한 후, 해당 조건에 맞게 두 포인터를 조정하면서 확인해 나갔다.

 

 

 

import sys

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

cnt = 0
for i in range(n):
    s, e = 0, n-1
    while s < e:
        if s == i:
            s += 1
        if e == i:
            e -= 1
        if s>=e:
            break

        temp = sub[s] + sub[e]
        if temp == sub[i]:
            cnt += 1
            break
            
        if sub[i] < temp:
            e -= 1
        else:
            s += 1
print(cnt)

 

---

 

두 포인터를 사용할 수 있는 좋은 예제 문제이다.