[백준] 1253번 좋다 - python 파이썬

문제

 

 

 

 

처음 이 문제를 접했을때는 배열에서 나올 수 있는 두 수의 합에만 집중을 한 나머지 combination을 활용해서 풀어주려고 했다.

그리고 이 풀이는 오답이였다.

 

왜냐하면 문제를 잘 읽어보면 다른 수 두개의 합으로 나타내는 것이 좋은 수 이다.

즉, 본인을 제외한(현재 인덱스를 제외한) 다른 두 수의 합으로 표현될 수 있는지를 찾아주어야 한다는 것이다.

 

때문에 조합을 이용해서 구해주게 되면 현재 인덱스가 사용된 합인지 아닌지를 알 수가 없기때문에 오답이 발생했던 것이다.

 

그래서 이를 해결하기 위해서는 투포인터를 사용해서 문제를 풀어주면된다.

 

 

n번씩 반복해서 현재 인덱스가 배열내에 다른 두 수의 합으로 표현되는지 확인해주면 된다.

 

풀이

import itertools
n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0

for i in range(n):
    goal = a[i]
    start = 0
    end = n-1

    while (start < end):
        now = a[start] + a[end]
        if now == goal:
            #현재 인덱스 예외처리
            if start == i:
                start += 1
            elif end == i:
                end -= 1
            else:
                ans+= 1
                break
        elif now > goal:
            end -= 1
        elif now < goal:
            start += 1
print(ans)