[백준 3273] 두 수의 합

문제

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

3273번: 두 수의 합

---

아이디어

투 포인터 기법을 이용하면 된다. 

수열의 길이가 최대 10만 개이기 때문에, for loop를 이용해서 하나하나 계산할 경우 최대 10^10번의 계산을 해야 한다.

 

이 경우 투 포인터 알고리즘을 이용할 수 있다.

문제에 주어진 설명을 빌려서 말하자면 양 끝에서 포인터를 좁혀가면서 조건에 맞는 모든 경우를 찾는 문제이다. 

하지만 단순히 양 끝에서 포인터를 좁혀나가면 안 되고, 리스트를 정렬해줘야 한다. 

 

이제부터는 예시를 가지고 살펴보자.

수열이 [5, 12, 7, 10, 9, 1, 2, 3, 11] 로 주어졌다고 하자. (예제 입력 1임)

정렬하면 [1, 2, 3, 5, 7, 9, 10, 11, 12] 이다. 그리고 x는 13이다.

 

그러면 양 끝점을 가지고 먼저 비교한다.

(1, 12)의 합은 13이기 때문에 조건을 만족한다. 

• 조건을 만족하는 경우 왼쪽 포인터(l), 오른쪽 포인터(r)를 가운데 방향으로 한 칸씩 옮긴다.
• l, r 둘 중 하나만 옮겨도 그 뒤의 연산은 나머지 하나를 옮기는 연산이어야 한다.
  • l을 오른쪽으로 옮기면 두 수의 합이 x보다 커지기 때문에 r을 왼쪽으로 옮겨야 한다. 
  • r을 왼쪽으로 옮기면 두 수의 합이 x보다 작아지기 때문에 l을 오른쪽으로 옮겨야 한다.

그 다음 조합은 (2, 11)이 된다. 마찬가지로 (2, 11)의 합은 13이기 때문에 또 l, r을옮긴다. 

 

그 다음 조합은 (3, 10)이 되고, 또 만족한다. 

 

그 다음 조합은 (5, 9)가 되고, 합이 14로 x보다 크다. 여기서 l을 옮기게 되면 합이 더 커지기 때문에 r을 옮겨야 한다. 

그러면 그 다음 조합은 (5, 7)이 되고, 합이 12로 x보다 작기 때문에 l을 옮겨서 합이 더 커지도록 해야 한다. 

그 다음 조합은 (7, 7)이 된다.

서로 다른 수의 조합을 찾는 것이기 때문에 이제부터는 고려할 필요가 없이 loop를 탈출하면 된다. 

탈출을 위한 조건을 부여한 부분이 while l < r : 이다. 두 수의 인덱스가 같아지면  연산을 멈춘다. 

---

Solution

n = int(input()) 
lst = list(map(int, input().split()))
lst.sort()
t = int(input())
answer = 0

l, r = 0, n-1
while l < r :
    Sum = lst[l] + lst[r]
    if Sum < t : 
        l += 1 
    elif Sum > t : 
        r -= 1 
    else : 
        answer += 1
        r -= 1
print(answer)