[백준] 1253번: 좋다

문제

백준 - 1253번: 좋다

분석

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

N이 최대 2000이다. 따라서 모든 조합을 구해놓고 판별하면 시간이 오래걸릴 뿐더러 어떤 수를 구할 때 자기 자신이 포함되어 있는지 확인하기 어렵다.

따라서 투 포인터를 사용한다.
먼저 입력받은 배열을 정렬하여 양쪽에서 포인터로 접근하는 방식을 택한다.
x 번째 수를 타겟이라고 했을 때 temp에 그 수를 빼고 리스트를 새로 만든다.
이렇게 하면 자기 자신이 포함되어 있는 경우를 고려하지 않아도 된다.
포인터가 가리키고 있는 두 값을 더하여 타겟 값이면 경우를 찾은 것이므로 break하고 다음 x에 대해 진행한다.
만약 타겟 값보다 크면 오른쪽 포인터를 하나 줄이고, 타겟 값보다 작다면 왼쪽 포인터를 하나 늘린다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline

n = int(input())
arr = sorted(list(map(int, input().split())))
cnt = 0
for x in range(n):
    temp = arr[:x]+arr[x+1:]
    i = 0
    j = n-2
    while i < j:
        val = temp[i] + temp[j]
        if val == arr[x]:
            cnt += 1
            break
        elif val > arr[x]:
            j -= 1
        elif val < arr[x]:
            i += 1
print(cnt)

끝으로..

투 포인터 문제를 풀어봤다.