[백준 1253] 좋다

1. 링크

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

2. 문제 설명

(1) 문제

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

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

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

 

(2) 입력

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

 

(3) 출력

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

 

3. 코드

#1253

import sys

#입력 받기
N = int(sys.stdin.readline().strip())
A = list(map(int, sys.stdin.readline().split(' ')))
count = 0
A.sort()

#투 포인터
for k in range(N):
    target = A[k]
    i = 0
    j = N - 1
    while i < j:
        if A[i] + A[j] == target:
            if i != k and j != k:
                count += 1
                break
            elif i == k:
                i += 1
            elif j == k:
                j -= 1
        elif A[i] + A[j] < target:
            i += 1
        else:
            j -= 1

print(count)

4. 설명

투 포인터를 활용한 문제이다. 2018 수들의 합과 거의 비슷하지만, 주어진 N개의 수가 정렬되어 있지 않으니 sort해주어야 하고, target이 되는 수가 자기자신을 통해 스스로를 합한다면 (ex. [0, 1, 2, 3, 4, 5]에서 5를 만드는 방법은 0+5, 1+4, 2+3이 있다. 이 때 0+5는 5가 target 자기자신이므로 count되지 않는다.) 그 경우를 제외해야 하므로 그 부분만 유의해서 코드를 작성하면 된다.

5. 배운 점

처음으로 푼(?) 골드 문제다. 교재에 나와있고 비슷한 투 포인터 문제여서 답안을 참고하면서 풀었는데, 생각보다 간단한 풀이여서 놀랐다. 골드 쪽 문제도 슬슬 도전해봐야겠다는 생각이 들었다:)