[Sliding Window] 백준 10025번 “게으른 백곰” Python 풀이

문제 링크

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

풀이

• 슬라이딩 윈도우 알고리즘을 활용하여 해결할 수 있습니다.
• 양동이의 좌표별 얼음 양은 1차원 배열에 저장합니다.
  • 1차원 배열의 크기는 최대 크기인 1000001로 생성합니다.
• 윈도우의 범위는 (2 * k) + 1 로 설정합니다.
  • 특정 위치에서 앞뒤로 k 만큼의 범위를 포함하기 때문입니다.
• 반복문을 돌며 윈도우 범위 내의 얼음의 양을 계산하고, 최댓값을 비교해나갑니다.
  • 윈도우를 한 칸씩 이동하며,
  • 윈도우의 맨 앞에 있었던 값은 윈도우의 합에서 빼고
  • 윈도우의 맨 뒤에 추가되는 값은 윈도우의 합에 더해줍니다.

코드

import sys

n, k = map(int, sys.stdin.readline().split(" "))

# 양동이의 좌표별 얼음의 양
ice = [0] * 1000001

# 마지막 양동이의 위치
last_idx = 0

# 양동이의 얼음 양과 위치 저장
for _ in range(n):
    value, index = map(int, sys.stdin.readline().split(" "))
    ice[index] = value

    # 마지막 양동이의 위치 저장
    last_idx = max(last_idx, index)

# 윈도우 범위
size = (2*k) + 1

# 윈도우 범위 내의 합 초기화
window = sum(ice[:size])

# 윈도우 범위 내의 최댓값 저장
answer = window

# end는 윈도우의 마지막 위치를 의미합니다.
for end in range(size, last_idx+1):

    # 윈도우의 맨 뒤에 추가되는 값은 윈도우의 합에 더하고
    # 윈도우의 맨 앞에 있었던 값은 윈도우의 합에서 빼줍니다.
    window += ice[end] - ice[end-size]
    answer = max(answer, window)

print(answer)