[백준 10025] 게으른 백곰

문제

더운 여름날 동물원의 백곰 앨버트는 너무 더워서 꼼짝도 하기 싫다. 다행히도 사육사들이 앨버트의 더위를 식히기 위해 얼음이 담긴 양동이들을 가져다 주었다. 앨버트가 가장 적은 거리만 움직이고도 최대한 많은 얼음으로 더위를 식힐 수 있도록 도와주자.

우리 안은 1차원 배열로 생각하며, 총 N(1 ≤ N ≤ 100000)개의 얼음 양동이들이 xi(0 ≤ xi ≤ 1,000,000)좌표마다 놓여 있고 각 양동이 안에는 gi(1 ≤ gi ≤ 10,000)씩의 얼음이 들어 있다. 일단 앨버트가 자리를 잡으면 그로부터 좌우로 K(1 ≤ K ≤ 2,000,000) 만큼 떨어진 양동이까지 닿을 수 있다. 앨버트는 양동이가 놓여 있는 자리에도 자리잡을 수 있다. 모든 얼음 양동이의 위치는 다르다.

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

 

입력

첫 줄에 정수 N과 K가 들어온다. 둘째 줄부터 N째 줄까지, 공백을 사이에 두고 각 양동이의 얼음의 양을 나타내는 gi와 양동이의 좌표를 나타내는 xi가 주어진다.

 

출력

앨버트가 택한 최적 위치로부터 K만큼 떨어진 거리 내에 있는 얼음들의 합(최댓값)을 출력한다.

---

접근

슬라이딩 윈도우 알고리즘을 공부한 후에 문제에 적용시켰다.

슬라이딩 윈도우는 특정 크기만큼의 창문을 옆으로 밀면서 해당 구간에 있는 값을 구한다고 생각하였다.

 

이를 위의 문제에서 적용시키면 다음과 같다.

1차원 리스트에서 특정 좌표의 좌, 우로 K만큼 더했을 때 최댓값을 구해야한다. 따라서 2*K+1 크기의 창문을 만든다.

그리고 해당 창문에 포함된 값들을 모두 더한 후에 최종해를 위한 최댓값 비교를 한다.

비교 후에는 맨 앞에있는 값을 빼고, 새로운 값을 뒤에 추가하여 한 칸씩 밀어준다고 생각한다.

 

구현

- 특정 좌표의 얼음 값을 numbers에 넣어준다.

- 탐색해야할 값의 최종 범위를 end에 넣어주기 위해 x의 최댓값을 비교하여 end에 넣어준다.

N, K = map(int, input().split())
numbers = [0] * 1000001
end = 0
for _ in range(N):
    g, x = map(int, input().split())
    numbers[x] = g
    end = max(end, x)

- step은 창문의 크기를 표현하고 크기는 2 * K + 1이 된다.

- 초기에 window에 0부터 step까지의 값들을 더해준다.

- 이제 step부터 끝까지 탐색을 하여 현재 값을 더해주고 window의 처음 값을 빼준다.

- 계속해서 answer와 window의 값을 비교하여 최댓값을 구한다.

step = 2 * K + 1
window = sum(numbers[:step])
answer = window

for i in range(step, end+1):
    window += numbers[i] - numbers[i-step]
    answer = max(answer, window)
print(answer)

---

전체 코드

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
numbers = [0] * 1000001
end = 0
for _ in range(N):
    g, x = map(int, input().split())
    numbers[x] = g
    end = max(end, x)

step = 2 * K + 1
window = sum(numbers[:step])
answer = window

for i in range(step, end+1):
    window += numbers[i] - numbers[i-step]
    answer = max(answer, window)
print(answer)