문제링크

1253 - 좋다

문제설명

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

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

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

문제풀이

투포인터를 사용해서 푼다.

1. N개의 수를 정렬
2. 0번째 수부터 N-1번째 수까지 투포인터를 이용해서 좋은 수인지 판단한다.
   2.1 start, end를 0, N-1로 둔다
   2.2 A[start]+A[end] == A[i]면 break
   2.3 > A[i]면 end --
   2.4 < A[i]면 start ++

근데 이렇게만 구현하면 0이 포함된 리스트에 대해서 0을 제외한 모든 수가 좋은 수라고 카운트된다. start 또는 end가 지금 검사하는 수가 아님을 체크하는 부분을 추가해야됨!

전체 코드는 다음과 같다.

import sys

input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
A.sort()

answer = 0
for i in range(len(A)):
    start, end = 0, len(A)-1
    while start < end:
        if start == i:
            start += 1
        elif end == i:
            end -= 1
        else:
            if A[start]+A[end] == A[i]:
                answer += 1
                break
            elif A[start]+A[end] < A[i]:
                start += 1
            else:
                end -= 1

print(answer)