[ BOJ 10025 ] 게으른 백곰(Python)

문제

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

n개의 얼음 양동이들이 좌표마다 놓여있고, 백곰은 좌우로 k만큼 떨어진 양동이까지 닿을 수 있다.
최적의 자리를 골랐을 때 닿는 얼음의 합을 구하면 된다.

제발 움직여 곰아!😓

문제 풀이

0. 입력 받기

• 딕셔너리를 이용해서 ice[좌표]=얼음 으로 값을 입력 받았다.
• 가장 왼쪽에 있는 좌표 min_l, 가장 오른쪽에 있는 좌표 max_l를 구했다.

n, k = map(int,input().rsplit())
ice = defaultdict(int)
min_l, max_l, answer = sys.maxsize, 0, -1

for _ in range(n):
    g, x = map(int,input().rsplit())
    ice[x] = g
    max_l = max(max_l, x)
    min_l = min(min_l, x)

1. 두 포인터 (start, end)를 움직이면서 값 구하기

• start 포인터, end 포인터의 범위는 좌표의 범위와 같다. [min_l ~ max_l]
• 특정 좌표 x에서 k만큼 좌우로 체크를 해야하므로, start가 x일때 범위는 [x-k, x+k] 이다.
  따라서 end - start 가 k*2 이하인 동안 end를 증가시키면 된다.
• ice[end] == 0 는 해당 좌표엔 얼음이 없다는 뜻이다.
  따라서 end를 뒤로 한 칸 이동시켜준다.
• 좌표에 얼음이 있을 땐 curr 에 얼음을 더해준 뒤 end를 한칸 뒤로 이동해준다.
• 가장 큰 curr 값을 answer에 저장해준다.
• start 포인터를 뒤로 이동시키기 위해 curr 값에서 start 포인터가 가리키는 값을 빼준다.

end, curr = min_l, 0

for start in range(min_l, max_l + 1):
    while end < max_l + 1 and end - start <= k * 2:
        if ice[end] == 0:
            end += 1
            continue
        curr += ice[end]
        end += 1
    answer = max(answer, curr)
    curr -= ice[start]

코드

import sys
from collections import defaultdict
input = sys.stdin.readline

# left, right : 양동이가 위치한 가장 좌측과 우측
# start, end : 투 포인터
# curr : 현재 얼음의 양

n, k = map(int,input().rsplit())
ice = defaultdict(int)
min_l, max_l, answer = sys.maxsize, 0, -1

for _ in range(n):
    g, x = map(int,input().rsplit())
    ice[x] = g
    max_l = max(max_l, x)
    min_l = min(min_l, x)

end, curr = min_l, 0
for start in range(min_l, max_l + 1):
    while end < max_l + 1 and end - start <= k * 2:
        if ice[end] == 0:
            end += 1
            continue
        curr += ice[end]
        end += 1
    answer = max(answer, curr)
    curr -= ice[start]
    

print(answer)