BOJ 1940. 주몽 (투 포인터)

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

1940번: 주몽

 

투포인터를 사용하기 위해서 중요한 전제 조건이 있는데 이는 데이터들이 정렬되어 있다는 조건이다.

이번 문제에서는 포인터를 시작과 끝에 두고 두 포인터가 서로 겹쳐지나가기 전까지만 반복문을 수행하게 된다.

 

예제를 정렬하면 1, 2, 3 ,4, 5, 7이 된다.

1 + 7은 8이라 9보다 작기 때문에 숫자를 높은 것을 더해야 하기 때문에 앞 포인터를 증가시키고

만약 3+7의 경우에는 9로 낮춰야하기 때문에 뒤 포인터를 감소시켜야 한다.

 

n = int(input())
total = int(input())
num_list = list(map(int, input().split()))


# 정렬
num_list.sort()

s = 0
e = n - 1
cnt = 0

while s<e:
    
    hap = num_list[s] + num_list[e]
    
    if hap > total:
        e -= 1
    elif hap < total:
        s += 1
    else:
        cnt += 1
        s += 1
        e -= 1
        
print(cnt)