[Python] 백준 / silver / 10025 : 배고픈 백곰

문제 링크 : https://www.acmicpc.net/problem/10025

오랜만에 슬라이딩 윈도우랑 투 포인터 두 가지 유형 동시에 복습하게 해준 문제. 슬라이딩 윈도우로 풀면 난이도는 쫌 더 쉽지만 메모리 낭비가 발생했다. 최적화의 관점에서 생각하면, 투 포인터 풀이가 조금 더 어렵지만 좋은 풀이인 것 같다.

투 포인터 풀 때는 for 문으로 start 를, 그 안의 while 문으로 end 를 조작한다는 걸 다시 한번 상기했다.

Python 코드 1 ( 슬라이딩 윈도우 )

import sys
N, K = map(int, sys.stdin.readline().split())

ice = [0] * (10**6+1)
for _ in range(N):
    g, x = map(int, sys.stdin.readline().split())
    ice[x] = g

answer = 0
window = 0

for i in range(2*K+1):
    if i > 10**6:
        print(window)
        exit(0)
    window += ice[i]

answer = max(answer, window)

for i in range(2*K+1, 10**6 + 1):
    window = window + ice[i] - ice[i - 2*K - 1]
    answer = max(answer, window)

print(answer)

Python 코드 2 ( 투 포인터 )

import sys
N, K = map(int, sys.stdin.readline().split())
ice = []

for _ in range(N):
    g, x = map(int, sys.stdin.readline().split())
    ice.append((x, g))

# 좌표, 얼음의 양
ice.sort(key=lambda x: x[0])

end = 0
answer = 0
interval_sum = 0
for start in range(N):
    while end < N and ice[end][0] - ice[start][0] <= 2*K:
        interval_sum += ice[end][1]
        end += 1

    answer = max(answer, interval_sum)
    interval_sum -= ice[start][1]

print(answer)