백준 1253번 Python 풀이

문제

 

시간 제한	메모리 제한	solved.ac 티어
2초	256MB	골드 4

---

풀이

이 문제도 밀린 문제이다. 언제 정리 다하나...

 

각설하고, 풀이를 해보겠다. 2467번이자 2470번 문제인 두 용액 문제(https://codejin.tistory.com/270)와 매우 유사한 문제이다. 해당 문제에서는 두 수의 합의 최솟값을 찾는 문제였지만, 이번 문제는 두 수의 합이 해당 배열에 존재하는지 여부를 따지는 문제이다. 유의할 점은 배열에 값이 같더라도 다른 값으로 본다는 점이다. 배열에 10이 두개 있고, 다른 두수의 합으로 10을 만들 수 있다면 이 두개 모두 좋은수이기 때문에 개수를 2개 올려줘야 한다. 입력받은 배열을 선형 탐색하면서, 원소 하나를 선택 한 후, 투포인터를 통해 해당 값을 만들 수 있는지 따져봐야 한다. 이때 배열에서 선택한 값을 또 고르지 않도록 포인터를 조정해야 한다.

코드

import sys
def input() : return sys.stdin.readline().strip()

n=int(input())
arr=sorted(list(map(int, input().split())))
cnt = 0

for i in range(n):
    l,r = 0,n-1
    while l < r:
        if l == i:
            l += 1
            continue
        elif r == i:
            r -= 1
            continue
        
        cur = arr[l] + arr[r]
        if cur == arr[i]:
            cnt += 1
            break
        elif cur < arr[i]:
            l+=1
        else:
            r-=1
print(cnt)