[백준 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만큼 떨어진 거리 내에 있는 얼음들의 합(최댓값)을 출력한다.

---

풀이

인덱스 에러로 나서 삽질을 한 문제이다. 슬라이딩 윈도우 유형을 다룰 때 인덱스 제어를 예민하게 해야 할 것 같다

K값의 범위도 상식 밖의 값이라 당황했던 것 같다

 

K가 3일 때 다음과 같이 얼음 양동이의 무게와 좌표를 입력받았다면

K*2+1 까지인

[0 0 0 5 2 0 7] 0 0 9 0 0 10

의 합을 maxIce변수에 넣어주고 시작한다

 

0 [0 0 5 2 0 7 0] 0 9 0 0 10

다음 값을 처리할 때는 nextIce변수를 사용하여 이전 값에 iceBucket[i] - iceBucket[i-(K*2+1)] 값을 더해주고 maxIce와 비교하여 최대 얼음량을 설정해준다

 

# 게으른 백곰
import sys
input = sys.stdin.readline
MAX_X = 1000001
N,K = map(int,input().split())
iceBucket = [0]*1000001

for _ in range(N):
    g,x = map(int,input().split())
    iceBucket[x] = g

maxIce = sum(iceBucket[:K*2+1])
nextIce = maxIce

for i in range(K*2+1,MAX_X):
    nextIce += (iceBucket[i] - iceBucket[i-(K*2+1)])
    if maxIce < nextIce:
        maxIce = nextIce

print(maxIce)

 

이전 수열문제와 다른 점이라 한다면 공간복잡도이다

수열문제에서는 이전값을 사용하여 다음 값을 결정하였고 그만큼의 리스트 공간을 더 썻다

게으른 백곰 문제에서는 이전값과 비교하여 최대 얼음량을 바로바로 재설정해주며 공간을 덜 사용했다