[BOJ 1253 🥇4] 좋다 (Python)

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

1253번: 좋다

문제

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

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

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

 

입력

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

 

출력

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

 

예제 입력 1 

10
1 2 3 4 5 6 7 8 9 10

 

예제 출력 1 

8

 

힌트

3,4,5,6,7,8,9,10은 좋다.

 

⭕ CODE

import sys

input = sys.stdin.readline

n = int(input())

arr = list(map(int,input().split()))

arr.sort()

result = 0

# i번째 숫자에 대한 확인
for i in range(n):

    # 각 숫자에 대해서 투포인터 탐색
    s = 0
    e = n-1

    # 서로 다른 두 숫자이므로 s가 e보다 작은동안만 
    while s < e:
    
    	# 두 수의 합이 i번째 숫자와 같다면
        if arr[s] + arr[e] == arr[i]:
            # i번째 숫자와 s번째 숫자가 같으면 불가능하므로
            if s == i:
            	# 시작지점 + 1
                s += 1
            # i번째 숫자와 e번째 숫자가 같으면 불가능
            elif e == i:
            	# 끝지점 - 1
                e -= 1
            # 그게 아니라면 가능한 경우이므로
            else:
            	# result + 1
                result += 1
                # 중단
                break
        # 두수의 합이 i번째보다 크다면 더 작아져야한다
        elif arr[s] + arr[e] > arr[i]:
            # 끝지점 - 1
            e -= 1
        # 두수의 합이 i번째보다 작다면 더 커져야한다 즉
        else:
            # 시작지점 + 1
            s += 1

# 결과 출력
print(result)

✏️ Comment

모든 숫자에 대해서 다른 두수의 합이 지금 조사하는 숫자와 같은지를 비교하는 방식을 사용하기 위해 투포인터를 사용했다.

문제의 조건 중 어떤 수가 다른 두수의 합이여서 i번째를 탐색한다면 시작지점 s 혹은 끝지점 e와는 달라야한다는 조건을 처음에 생각하지 못하였다.