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 = map(int, input().split())
zoo = [list(map(int, input().split())) for _ in range(N)]
arr = [0 for _ in range(1000001)]
for i in range(N):
arr[zoo[i][1]] = zoo[i][0]
step = K * 2 + 1
tmp = sum(arr[:step])
result = tmp
for i in range(step, 1000001):
tmp += arr[i] - arr[i-step]
result = max(result, tmp)
print(result)💡 한마디
좌표에 양동이의 얼음 양을 저장해두고 sliding window 기법을 이용해 풀었다.
