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

1. 코드

"""
https://www.acmicpc.net/problem/1253
- 음수값 고려
- 오름차순 정렬
- 포인터가 두 수로 만들려는 값(target)의 인덱스일 경우 continue

질문에서 찾은 예외 케이스)
3
-5 -2 -3
정답: 1

3
0 0 0
정답: 3

3
0 0 1
정답: 0

13
-30 -10 -8 -5 -2 0 2 4 6 8 10 18 20
정답: 11
"""

import sys

ans = 0
n = int(input())
nums = list(map(int, sys.stdin.readline().rstrip().split()))
nums.sort()

for target in range(len(nums)):
    # 자기 자신을 만날 경우 continue 로 한 칸 건너 뛰기 때문에 
    # 첫 항과 마지막 항에 대해 예외처리를 하지 않아도 된다.
    left = 0
    right = len(nums) - 1
    while left < right:
        # 포인터가 target 일 경우 한 칸 건너뛴다.
        # continue 를 하면 left < right 조건을 다시 체크할 수 있다.
        if left == target:
            left += 1
            continue
        if right == target:
            right -= 1
            continue

        if nums[left] + nums[right] == nums[target]:
            ans += 1
            # print(f'target={nums[target]}, left_idx={left}, right_idx={right},'
            #       f' left={nums[left]}, right={nums[right]}')
            break
        if nums[left] + nums[right] < nums[target]:
            left += 1
        else:
            right -= 1
print(ans)

2. 후기

DP로 풀어볼까 했지만 1,000,000,000 크기의 리스트를 사용하는 DP는 존재하지 않는다.

일반적으로 파이썬에서 N=2000이라면 O(n^2)의 시간 복잡도를 사용할 수 있다.

그렇다고 무식하게 O(n^2)를 사용하는 문제는 아닐거라는 생각을 했고 투 포인터로 접근하여 문제를 풀었다.