[백준] #1253 좋다(python)

📌문제

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

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

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

입력

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

출력

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

예제 입력

10
1 2 3 4 5 6 7 8 9 10

예제 출력

8

백준 1253번 문제

💡Idea

생각보다 많은 것들을 고려해주어야 하는 문제입니다.

우선 가장 단순하게는, 자기 자신보다 작은 수들의 모든 조합으로 구할 수 있는 모든 덧셈값을 구한 다음, 그 중에 자신의 값이 있는지를 확인하는 방법입니다.

import sys
from itertools import combinations

input = sys.stdin.readline

N = int(input())
A = sorted(list(map(int, input().split())))
ans = 0
for i in range(N):
    sum_set = set(sum(value) for value in list(combinations(A, 2)))
    if A[i] in sum_set: ans += 1
print(ans)

하지만 이와 같은 방법은 시간 초과가 발생합니다.

따라서, 투✌ 포인터를 이용하여 문제를 해결해보았습니다.

투 포인터를 사용하기 위해서는 A 리스트의 숫자들을 먼저 정렬해주어야 합니다.

그리고, 두 개의 포인터는 각각 자기 자신을 제외한 A 리스트의 맨 앞과 맨 뒤에서 시작합니다.

A[i]가 다른 두 수의 합으로 나타낼 수 있는지를 확인하는 경우,

• A[left] + A[right] > A[i] 이면 right를 1 감소해줍니다.
  ➡ 두 값을 더했을 때 A[i]보다 더 큰 값이기 때문에, 더 작은 값으로 만들어주기 위해서 큰 값인 right를 1 감소해줍니다.
  $\;$
• A[left] + A[right] < A[i] 이면 left를 1 증가해줍니다.
  ➡ 두 값을 더했을 때 A[i]보다 더 작은 값이기 때문에, 더 큰 값으로 만들어주기 위해서 작은 값인 left를 1 증가해줍니다.

💻코드

• ⏰ 시간 : 1192 ms / 메모리 : 30840 KB

import sys
input = sys.stdin.readline

N = int(input())
A = sorted(list(map(int, input().split()))) # 정렬된 N개의 수
ans = 0
for i in range(N): # 모든 N개의 숫자에 대해서 확인
    target_num = A[i]
    Ai = A[:i] + A[i+1:] # 자기 자신을 제외
    left, right = 0, N - 2
    while left < right:
        sum_value = Ai[left] + Ai[right]
        if sum_value > target_num: # 두 값의 합이 큰 경우 right 1 감소
            right -= 1
        elif sum_value < target_num: # 두 값의 합이 작은 경우 left 1 증가
            left += 1
        else: # 두 값의 합이 A[i]인 경우 종료
            ans += 1
            break
print(ans)