1253 좋다

🥇 1253 좋다

문제

---

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.

N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.

수의 위치가 다르면 값이 같아도 다른 수이다.

입력

---

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

출력

---

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

분석

---

nums 리스트에 저장되는 숫자들은 중복이 허용된다. 문제에서 수의 위치가 다르면 값이 같아도 다른 수라고 명시했기 때문이다. 기존의 투 포인터처럼 먼저 정렬을 한다음 포인터 두개를 둔다.

• L: 리스트 0부터 시작
• R: 리스트의 뒤부터 시작

2개의 수를 더해서 리스트에 있는 숫자(target)를 만드는 것이다. 여기서 주의해야할 점은 target을 더할 때 사용하면 안된다는 것이다.
따라서 target의 인덱스를 제외하고 더할 수 있도록 조건을 추가해 주었다.

소스 코드

---

import sys
input = sys.stdin.readline

N = int(input())
nums = list(map(int, input().split()))

nums.sort()

result = 0
for i in range(N): # 현재 target의 인덱스는 스킵해야함
    L, R = 0, N - 1
    total = 0 # 2개의 숫자를 더해 nums[i]를 만들어야 함
    while L < R:
        total = nums[L] + nums[R]

        if L != i and R != i and total == nums[i]:
            result += 1
            break

        if L == i or total < nums[i]:
            L += 1
        elif R == i or total >= nums[i]:
            R -= 1

print(result)