[백준 1253 🥇] 좋다

문제

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

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

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

입력

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

출력

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

문제풀이

import sys

n=int(sys.stdin.readline())
numbers=list(map(int, sys.stdin.readline().strip().split(' ')))
numbers.sort()
ans=0

for idx in range(n):
    start=0
    end=n-2
    value=numbers[idx]
    tmp_numbers=numbers[:idx]+numbers[idx+1:]
    while start<end:
        sum_value=tmp_numbers[start]+tmp_numbers[end]
        if sum_value==value:
            ans+=1
            break
        elif sum_value<value:
            start+=1
        elif sum_value>value:
            end-=1

print(ans)

numbers에 존재하는 모든 값들에 대해서 투 포인터를 이용해서 해당 수를 두 수를 더해서 만들 수 있는지 확인한다.

 

0. 투 포인터를 사용하기 위해서 입력받은 수들을 오름차순 정렬한다. 

1. 0번부터 n-1번 인덱스까지 for문을 돌면서 모두 탐색한다.

2. for문 안에서 idx번 숫자 제외하고 저장한 배열 tmp_numbers를 투 포인터로 돌면서 idx번 숫자를 만들 수 있는지 확인한다.

3. start=0, end=n-2(tmp_numbers의 마지막 인덱스)로 초기셋팅을 하고, idx번 숫자는 변수 value에 저장한다.

4. 서로 다른 수끼리 더하는 경우만 탐색하기 위해서 start<end일 동안만 while문을 반복하도록 한다.

5. while문 안에서는 변수 sum_value에 현재 start와 end에 해당하는 tmp_numbers의 숫자를 더해서 저장하고, sum_value가 우리가 찾는 value값과 동일한지 확인한다. 

6. 동일하다면, 좋은 수의 개수(ans)를 +1해주고, 이미 좋은 수인 것이 결정됐으므로 더 이상 해당 수에 대한 while문을 반복할 필요가 없기 때문에 break로 while문을 빠져나온다.

7. sum_value가 value보다 작다면, start+=1해주고 더 큰 값을 탐색하도록 한다.

8. sum_value가 value보다 크다면, end-=1해주고 더 작은 값을 탐색하도록 한다.

9. 이 과정을 반복하면서 모든 숫자들을 탐색하고, 계산된 좋은 수의 개수를 출력하고 종료한다.