투 포인터 예제

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

 

N, M = map(int,input().split())
A = list(map(int, input().split()))


# 1. 합 < M : 끝점을 +1 이동시킴
# 2. 합 >= M : 시작점을 +1
start = 0
end = 0
sum = A[0]

count = 0

while True:
    # 현재 구간 합이 M인지 확인
    if sum == M:
        count += 1
        
    # 구간 업데이트
    if sum >= M:
        start += 1
        sum -= A[start-1]
    else:
        if end == N-1: # 끝점 +1 하려는데 구간 종료될 상황이라면
            break
        end += 1
        sum += A[end]
        
print(count)

 

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

일반적으로 A, B 정렬 후 비교하면 두 가지 문제

1. B 종이 더 큰게 명백해도 계속 비교

2. A 종이 더 큰게 명백해도 계속 비교

 

A에 main 포인터, B에 sub 포인터 위치시킴

B의 sub 포인터의 인덱스 = 자기 앞의 원소의 개수입니다.

 

# 1. a > b 이면 sub를 +1
# 2. a <= b 이면 main을 +1, 답 += sub의 인덱스

T = int(input())

for _ in range(T):
    N, M = list(map(int, input().split()))
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    
    A = sorted(A)
    B = sorted(B)
    
    main = 0
    sub = 0
    count = 0
    
    while main < N:
        if sub == M:
            count += sub
            main += 1
        else:
            if A[main] > B[sub]:
                sub += 1
            else:
                main += 1
                count += sub
    print(count)