[Sliding Window] BOJ 10025 게으른 백곰

 

🎈 백준 10025 게으른 백곰

www.acmicpc.net/problem/10025

10025번: 게으른 백곰

 

❗ 문제의 핵심, 풀이 과정

• x 좌표마다 양동이가 있고, 각 양동이 안에는 g씩의 얼음이 들어있다.

=> arr 배열을 초기화하고, arr[x] = g 으로 입력값을 받는다.

 

• 앨버트가 최적의 자리를 골랐을 때 얼음의 합을 구하시오. 즉, 얼음들의 합의 최댓값을 구해야 한다.

=> 엘버트의 닿을 수 있는 거리의 마지막 원소가 주어진 x 좌표의 최대값만큼 이동했을 때까지 고려해야한다. 

     - 좌표의 최대값 max_x를 구한다. 

 

• 엘버트가 자리를 잡으면 좌우로 k만큼 떨어진 양동이까지 닿을 수 있다.

=> 총 2*k+1만큼의 범위까지의 얼음의 합을 구할 수 있다.

=> 범위가 2*k+1로 지정되어있고, 범위를 한칸씩 이동시키며 범위의 끝이 max_x 에 도달하면 종료한다.

     - 범위는 큐를 이용하여 슬라이딩 윈도우를 사용한다.

     - 큐 안의 임시 얼음들의 합을 temp라고 정하고, temp의 변경이 있을 때마다 최대합 max_value를 업데이트 한다.

 

 

백준 예제 1) n = 4, k = 3

 

arr 배열 (arr[x] = g)

 

큐 과정

 

temp = 0, max_value = 0

 

 

...

temp = 7, max_value = 7

 

 

...

temp = 7, max_value = 7

 

 

...

temp = 11, max_value = 11

 

 

...

temp = 10, max_value = 11

 

 

max_value = 11

 

✅ 전체 코드

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

arr = [0] * 1000001     # arr[i] = 좌표가 i일때의 얼음 g
n, k = map(int, input().split())
queue = deque()

max_x = 0   # 좌표 최대값
for i in range(n):
    g, x = map(int, sys.stdin.readline().split())
    arr[x] = g
    if x > max_x:
        max_x = x

max_value = 0   # 얼음들의 최대합
temp = 0    # 범위 안의 임시 얼음들의 합
# 슬라이딩 윈도우 방법
for x in range(max_x + 1):  # 엘버트의 좌표 이동
    # 엘버트가 닿을 수 있는 거리보다 큐의 크기가 작으면 현재 좌표의 얼음 추가
    if len(queue) < 2 * k + 1:
        queue.append(arr[x])
        temp += arr[x]
        max_value = temp
    # 큐에서 pop한만큼 얼음의 임시 합에서 빼주고, 현재 좌표의 얼음추가
    else:
        temp -= queue.popleft()
        queue.append(arr[x])
        temp += arr[x]
        if temp > max_value:    # 얼음들의 최대합 업데이트
            max_value = temp

print(max_value)