[Python/파이썬] 백준 1253번 좋다

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

코드

import sys
input = sys.stdin.readline

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

arr.sort()
ans = 0
for i in range(n):
    l, r = 0, n-1
    while l < r:
        if l == i:
            l += 1
        if r == i:
            r -= 1
        if l >= r:
            break
        if arr[l]+arr[r] == arr[i]:
            ans += 1
            break
        elif arr[l]+arr[r] < arr[i]:
            l += 1
        else:
            r -= 1
print(ans)

 

설명

1. 처음 입력으로 주어진 배열 arr를 오름차순 정렬한다.

2. 정렬된 arr의 첫번째 원소부터 좋은 수인지 판별한다.

    a. 투포인터로 검색을 할 범위의 시작과 끝을 나타내는 변수 l, r을 선언한다.

    b. l < r인 동안 l과 r의 범위를 줄여나가며 arr[l]+arr[r] == arr[i]가 되는 경우가 있는지 확인한다. 만약 arr[l]+arr[r]이 arr[i]보다 작다면 합을 증가시키기 위해 l을 왼쪽으로 이동시키고, 반대의 경우에는 합을 감소시키기 위해 r을 왼쪽으로 보내면 된다. 이때, l과 r은 i와 같을 수 없으므로 i와 같아지는 경우에는 범위를 줄이는 쪽으로 한 칸 이동시키면 된다.