Concept

이 문제는 구간합의 최댓값을 구하는 문제이다.
그러나 이 문제의 특이점은 구간합의 기준인 좌표가 연속적으로 제공되지 않았다는 점이다.
그래서 구간합을 구하는 대표적인 알고리즘인 누적합보다 투포인터를 이용하면 더 좋을 것 같다고 판단했다.
투포인터를 이용하여 구간합을 구하되,
반복적인 구간합 계산을 피하기 위해
투포인터를 업데이트할 때만 포인터가 위치한 위치의 값을 더하거나 빼는 방식을 택했다.

Process

• 우선 얼음의 위치를 오름차순으로 정렬한 후
• 구간 길이가 2*k 이하인 구간을 투포인터를 통해 정의
  • 구간 길이가 2*k 이하인 경우 end 포인터를 계속 오른쪽으로 옮기고
  • 2*k를 초과하면 start 포인터를 오른쪽으로 옮김
  • 이렇게 하면 투포인터로 정의된 구간이 슬라이딩 윈도우처럼 배열 시작부터 끝까지 오른쪽으로 이동할 수 있다
• 포인터가 이동하여 구간이 변경되면 구간합을 업데이트함
  • end 포인터가 업데이트된 경우 구간합인 window_sum에 end 포인터의 값을 더함
  • start 포인터가 업데이트하는 경우 예전 start 포인터 값이 구간에서 벗어난 거기 때문에 예전 start 포인터 값을 뺴고, start 포인터 값을 업데이트함
• 구간합이 바뀔 때마다 구간합 최댓값을 업데이트함
• 마지막으로 구간합 최댓값을 출력

Point

• 투 포인터 문제는 언제 탐색 멈추는 조건이 매우 중요
• 특히, start <= end 조건을 넣는 게 좋다..!

코드

import sys

input = sys.stdin.readline

if __name__ == "__main__":
    n, k = map(int, input().split())
    waterbkt = []
    max_sum = 0

    for _ in range(n):
        waterbkt.append(list(map(int, input().split())))
    waterbkt.sort(key=lambda x: x[1])

    start, end, window_sum = 0, 0, 0
    while start <= end and end < n:
        if waterbkt[end][1] - waterbkt[start][1] <= 2*k:
            window_sum += waterbkt[end][0]
            max_sum = max(max_sum, window_sum)
            end += 1 
        else:
            window_sum -= waterbkt[start][0]
            start += 1
    print(max_sum)