백준 1253 좋다

haruponea·2021년 4월 3일
0

BOJ

목록 보기
32/41

문제 링크https://www.acmicpc.net/problem/1253

풀이
리스트를 입력받고 정렬한 리스트의 원소를 target으로 탐색을 하면 풀리는 문제였습니다. 단 탐색할때 target의 원소는 제외해야하고 이분탐색처럼 반으로 하면 안되고 left, right를 한 칸씩 움직이며 target을 찾아야 합니다.

Python

import sys
n = int(sys.stdin.readline())
dic = {}
l = list(map(int, sys.stdin.readline().split()))
cnt = 0
if n <= 2:
    print(0)
    sys.exit()
l.sort()
for i in range(n):
    target = l[i]
    left, right = 0, n-1
    while left < right:
        if right == i:
            right -= 1
            continue
        if left == i:
            left += 1
            continue
        sum = l[left] + l[right]
        if sum == target:
            cnt += 1
            break
        elif sum < target:
            left += 1
        else:
            right -= 1
print(cnt)

0개의 댓글