파이썬) 좋다 - BOJ

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

1253번: 좋다

 

문제는 arr[i]가 arr에 있는 수들 중 두개의 수의 합으로 만들어 질수있다면 arr[i]는 "좋다"라고 한다

arr에 있는 "좋다"의 갯수를 구하는 문제이다.

 

애초에 문제 설명부터 투포인터를 사용하세요.라고 설명이 되어있는 듯하다.

그러나 |Ai| ≤ 1,000,000,000, Ai는 정수)라고 되어있는 조건문 때문에 처음에 투포인터를 생각했다가 이분탐색으로 생각을 돌렸다.

나는 투 포인터로 풀었기 때문에 투 포인터로 설명해보겠다.

 

우선 arr안에 있는 "좋다"를 구하기 위해선 arr을 반복문으로 모든 수를 돌며 "좋다"인지 아닌지 확인해야 하기에 반복문을 돌아야한다.

 

이를 arr[i]로 나타내면, arr[i]는 i번째 수를 제외한 나머지 수들 중에서 두 수를 더해 arr[i]의 값이 나오는지 확인해야한다.

 

즉 arr을 반복문으로 돌며 i번째 인덱스를 제외한 나머지로 새 배열을 만들고 이 배열에 투포인터를 적용해 두 수의 합이 arr[i]가 되는지 확인하면 된다.

 

n = int(input())

arr = list(map(int, input().split()))
arr.sort()

answer = 0

for i in range(n):
    # i인덱스 제외
    temp = arr[:i] + arr[i+1:]
    left = 0
    right = len(temp) - 1

    while left < right:
        # 투 포인터
        num = temp[left] + temp[right]

        if num == arr[i]:
            answer += 1
            break
        elif num > arr[i]:
            right -= 1
        else:
            left += 1

print(answer)