(Python/🥇4)백준알고리즘 1523번 : 좋다

728x90

문제 바로가기

문제:

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다. N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라. 수의 위치가 다르면 값이 같아도 다른 수이다.

입력:

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

출력:

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

풀이:

import sys

n = int(input())
lst = sorted(list(map(int, sys.stdin.readline().split(" "))))
res = 0
for i in range(len(lst)):
    target = lst[i]
    start = 0
    end = n - 1
    while start < end:
        sum = lst[start] + lst[end]
        if sum == target:
            if start != i and end != i:
                res += 1
                break
            elif i == start:
                start += 1
            elif i == end:
                end -= 1
        elif sum < target:
            start += 1
        else:
            end -= 1
print(res)

이 문제는 투포인터를 사용해서 풀어주었다.

하지만 자기 자신은 뺀 합 이여야한다. 그래서 start != i 이고 end != i 아니여야 한다.

그 것을 제외하고는 start와 end 값을 조정하면 된다.