[백준 / DP] 1253 : 좋다 (python)

문제 설명

문제

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

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

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

입력

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

출력

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

예제 입력 1

10
1 2 3 4 5 6 7 8 9 10

예제 출력 1

8

힌트

3,4,5,6,7,8,9,10은 좋다.

풀이

import sys
input = sys.stdin.readline
N = int(input())
A = sorted(list(map(int, input().split())))
cnt = 0

for n in range(N):
    i, j = 0, N-1
    find = A[n]
    while(i < j):
        if A[i] + A[j] < find:
            i += 1
        elif A[i] + A[j] > find:
            j -= 1
        else:
            if j == n:
                j -= 1
            elif i == n:
                i += 1
            else:
                cnt += 1
                break

print(cnt)

• 숫자 범위 내에 음수도 포함된다는 점을 유의해야한다. 음수 포함된 줄 모르고 j = n-1로 시작했다가 계속 틀렸다.
• 우선 입력받은 수는 배열로 받아 정렬한다. 그리고 N만큼 for문을 돌면서 해당 배열의 n인덱스가 좋은 수인지 체크한다. 이때 투 포인터를 사용하여(i, j) i와 j가 교차되는 순간이 올때까지 while문을 돌면서 체크한다.
• i(시작 인덱스)는 0, j(끝 인덱스)는 N-1부터 시작하여 A[i] + A[j]가 n이 되는지 찾는다.
  • A[i] + A[j] < find 일 경우(이때 find는 A[n]), 더한 값이 더 커져야하므로 i를 +1한다.
  • A[i] + A[j] > find 일 경우, 더한 값이 더 작아져야하므로 j를 -1한다.
  • A[i] + A[j] == find 일 경우, j와 i가 n이 아닐때 (자기 자신은 포함하지 않아야 함) cnt를 +1하고 while문을 종료한다.