[백준] 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

4 3
4 7
10 15
2 2
5 1

예제 출력 1

11

제출 답안

• 슬라이딩 윈도우라는 기법을 사용해서 풀어야 한다.
• https://kimmeh1.tistory.com/404
• 위 블로그를 참고하였다.
• 슬라이딩 윈도우 기법을 공부해야 겠다.

'''
1. 아이디어
- 슬라이딩 윈도우를 하기 위해 값을 저장한다.
- 처음 위치부터 end +1 까지 비교해나간다.
2. 시간 복잡도
- 
3. 변수
- graph []
'''

import sys

input = sys.stdin.readline


n, k = map(int, input().split())
graph = [0] * 1000001
end = 0
for _ in range(n):
    a, b = map(int, input().split())
    graph[b] = a
    end = max(end, b)

idx = 2 * k + 1
temp = sum(graph[:idx])
result = temp

for i in range(idx, end+1):
    temp += graph[i] - graph[i-idx]
    result = max(result, temp)

print(result)
```었다. 앨버트가 가장 적은 거리만 움직이고도 최대한 많은 얼음으로 더위를 식힐 수 있도록 도와주자.

우리 안은 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

4 3
4 7
10 15
2 2
5 1

##### 예제 출력 1

11

> ### 제출 답안

-   슬라이딩 윈도우라는 기법을 사용해서 풀어야 한다.
-   [https://kimmeh1.tistory.com/404](https://kimmeh1.tistory.com/404)
-   위 블로그를 참고하였다.
-   슬라이딩 윈도우 기법을 공부해야 겠다.

'''

1. 아이디어

• 슬라이딩 윈도우를 하기 위해 값을 저장한다.
• 처음 위치부터 end +1 까지 비교해나간다.

2. 시간 복잡도

3. 변수

• graph []
  '''

import sys

input = sys.stdin.readline

n, k = map(int, input().split())
graph = [0] * 1000001
end = 0
for _ in range(n):
a, b = map(int, input().split())
graph[b] = a
end = max(end, b)

idx = 2 * k + 1
temp = sum(graph[:idx])
result = temp

for i in range(idx, end+1):
temp += graph[i] - graph[i-idx]
result = max(result, temp)

print(result)
```