[백준] 1253 좋다 (파이썬 python)

 

 

문제 링크

 

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

1253번: 좋다

 

 

 

문제 풀이

 

간단한 이분탐색 문제 같지만 생각할 예외가 있는 문제였습니다.

처음에는 단순히 배열을 정렬한 후 초기 start를 0, end를 현재 확인하고 있는 인덱스의 앞까지로 해서

이분탐색을 진행하면 되지 않을까 했습니다.

하지만 이렇게 할 경우 아래 테케와 같이 동일한 숫자가 여러 개일 경우 문제가 발생합니다.

4

0 0 0 0

1번 0은 뒤에 있는 0들을 더해서 만들 수 있는 숫자임에도 인덱스 범위로 인해 만들 수 없는 숫자로 판별됩니다.

이에 따라, bisect_left로 현재 숫자의 가장 끝 인덱스를 구한 뒤 end에 넣어 이분탐색을 진행하려 했습니다.

하지만 문제에서 주어진 숫자는 절댓값 범위가 주어져 음수도 가능합니다.

음수의 경우 큰 숫자 두개를 더해서 더 작은 숫자를 만들 수 있기 때문에 (ex : -1 + (-2) = -3)

bisect를 이용한 범위 설정에 오류가 생기게 됩니다.

결국 안전하게 전체 범위에 대해 이분 탐색을 진행하되,

start, end가 현재 숫자의 인덱스일 경우 범위를 조정하는 방식으로 구현했습니다.

 

n = int(input())
arr = list(map(int, input().split()))
arr.sort()
result = 0
for i in range(n):
    start, end = 0, n - 1
    while start < end:
        if start == i:
            start += 1
            continue
        if end == i:
            end -= 1
            continue
        if arr[start] + arr[end] < arr[i]:
            start += 1
        elif arr[start] + arr[end] > arr[i]:
            end -= 1
        else:
            result += 1
            break
print(result)