[Python][백준/BOJ] 10025번 : 게으른 백곰

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

10025번: 게으른 백곰

 

내 코드

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
ice = [0 for i in range(1000001)]
last =0
for i in range(n):
    a, b = map(int, input().split())
    ice[b] = a
    last = max(last, b)

window_size = 2*k+1
window = sum(ice[:window_size]) # 오른쪽을 움직인다고 생각하기
ans = window 

for i in range(window_size, last+1):
    window += ice[i] - ice[i-window_size]
    ans = max(ans, window)
print(ans)

 

코드 리뷰

슬라이딩 윈도우

해당 문제는 기본 개념 문제보다는 조금 더 까다롭게 느껴졌던 문제이다. 

범위가 주어지기 때문인데, 주인공은 서있는 자리로부터 -k, +k가 가능하다.

이 경우에 부분 합의 최댓값을 찾는 것이라서, 이 부분을 잘 해결해야 하는 것 같다.

window_size = 2*k+1
window = sum(ice[:window_size]) # 오른쪽을 움직인다고 생각하기

그래서 나는 윈도우 크기를 2*k+1 로 해주었다. 

슬라이딩 윈도우는 무조건 윈도우의 가장 오른쪽 끄트머리를 잡고 움직인다고 생각하자.

0이 시작 지점이라면, 내가 아예 안 움직였을 때도 나의 윈도우는 2*k+1 인 것이다.( k만큼의 왼쪽, 오른쪽인 2*k+ 내가 서있는 현재 자리인 1)

이렇게 생각하면 앞으로의 코드 설계는 꽤 순탄하다.

슬라이딩 윈도우를 공부하고 싶을 때 응용편으로 조금 생각해보기 좋은 문제같다.