[백준/S4] 1253 좋다

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

31120 912 Python 3

import sys
input = sys.stdin.readline

# 어떤 수가 다른 수 두개의 합으로 나타날 수 있을 때
# 이 때, 어떤 수에는 음수도 포함됨
N = int(input())
arr = list(map(int, input().split()))
arr.sort()
ans = 0



# for문으로 하나씩 검사
for i in range(N):
    sum_num = arr[i]
    l = 0
    r = N - 1

    while l < r:

        temp = arr[l] + arr[r]

        if temp == sum_num:

            if l == i:
                l += 1

            elif r == i:
                r -= 1

            # l과 r이 목표한 값의 인덱스와 같은 경우들을 제외하면 성립
            else:
                ans += 1
                break

        elif temp < sum_num:
            l += 1

        else:
            r -= 1

        
print(ans)

조건을 대충 읽고... 음수가 포함되지 않는 형태로 풀었다가 한참 헤맸다
거기서...심지어 또 헤맸는데 사실 조건을 확인해보면 N(1 ≤ N ≤ 2,000)였으니 for문 하나쯤 추가해도 괜찮은 조건이었다

• 총 nlogn의 시간복잡도