BOJ 1253번: 좋다

www.acmicpc.net/problem/1253

1253번: 좋다

아이디어:

뭔가 일단 정렬을 해야 할 것 같다.

근데 이걸 투 포인터로 어떻게 풀 수 있을까?

모든 경우를 찾아본다면, 가능한 두 수를 모두 뽑고 그 합과 같은 숫자가 있는지 탐색할 수 있을 것이다. 탐색은 이분 탐색이 가능할 것 같다. 근데 이게 시간 안에 풀어질까..?

그래서 구글링함^^

내 생각이 조금은 맞았다. 대신 반대로, arr에 있는 모든 수를 돌면서 합이 arr[i]가 되는 두 수가 있는지를 찾는다. 이때 투 포인터를 이용한다. 아, 아무래도 내 생각대로면 이분탐색을, 이 방법으로는 투 포인터를 이용하는 건가? 

 

코드 구현과정에서 맞았을때 탈출하는 조건을 안써서 애먹었다..ㅠㅠ

import sys
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))

arr.sort()
ans = 0

for i in range(n):
    left, right = 0, n-1
    #투포인터
    while (True):
        if (left>=right): break
        result = arr[left]+arr[right]
        
        if (result > arr[i]):
            right-=1
            
        elif (result < arr[i]):
            left+=1
            
        else:
            if (left!=i and right!=i): #자기자신과 더하는 값이 같으면 안되므로
                ans+=1
                break #탈출조건 주의
            elif (left==i):
                left+=1
            elif (right==i):
                right-=1
print(ans)