[백준] 게으른 백곰 / 10025번 / 파이썬 / Python / Sliding Window / 슬라이딩 윈도우

 

💡solutions )

 

💬 슬라이딩 윈도우 알고리즘(Sliding Window)을 활용하여 문제를 해결하였다.

💬 먼저 얼음 양동이들을 나타내는 ice 배열을 최대 크기만큼 만들어준다. -> ice = [0]*1000001

💬 입력을 주어진 양동이 좌표에 해당하는 얼음의 양을 넣어준다.

💬 윈도우의 고정된 범위를 next = 2*k +1(한 좌표에서 앞뒤로 k만큼씩 떨어지는 있는 범위를 모두 포함하므로)로 두고, for 반복문을 돌려 한칸씩 이동하며 맨 뒤에 있는 값 ice[i]은 윈도우값에서 (+)더해주고 맨 앞에 있는 값 ice[i-next]은 (-)빼준다.

💬 window값 업데이트할 때마다 answer도 최대값으로 업데이트해주기

 

📚 슬라이딩 윈도우 알고리즘(Sliding Window)이란? 윈도우 즉 일정한 범위를 가지고 있는 것을 유지하면서 이것을 이동(sliding) 하는 것이다. 배열이나 리스트의 요소의 일정 범위의 값을 비교할때 사용하면 유용한 알고리즘이다. 매번 처리되는 중복된 요소를 버리지 않고 재사용함으로써 낭비되는 계산을 하지 않음으로써 효율적으로 처리하는 방법입니다. 출처 및 참고 블로그

📌비슷한 유형의 문제 풀어보기👇 백준 2559번 수열

 

 

👨‍💻code )

import sys

input = sys.stdin.readline
n, k = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
ice = [0]*1000001
for i in range(n):
    ice[arr[i][1]] = arr[i][0]

next = 2*k + 1
window = sum(ice[:next])
answer = window

for i in range(next, 1000001):
    window += (ice[i] - ice[i-next])
    answer = max(answer, window)
print(answer)

 

 

📌description )

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

---