[백준] 10025 게으른 백곰 with Python

📌 BOJ 10025 게으른 백곰

💡 조건

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

2. 우리 안은 1차원 배열로 생각하며, 총 N개의 얼음 양동이들이 xi좌표마다 놓여 있고 각 양동이 안에는 gi씩의 얼음이 들어 있다.
   (1 ≤ N ≤ 100000)
   (0 ≤ xi ≤ 1,000,000)
   (1 ≤ gi ≤ 10,000)

3. 앨버트가 자리를 잡으면 그로부터 좌우로 K(1 ≤ K ≤ 2,000,000) 만큼 떨어진 양동이까지 닿을 수 있다.
   앨버트는 양동이가 놓여 있는 자리에도 자리잡을 수 있다.
   모든 얼음 양동이의 위치는 다르다.

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

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

6. 누적합, 슬라이딩 윈도우 유형의 문제

🔖 예제 및 실행결과

예제 1

4 3
4 7
10 15
2 2
5 1

실행결과 1

11

⌨️ 문제 풀이

1. 이 문제는 두 가지 풀이를 할 수 있는데, 나는 슬라이딩 윈도우로 풀이했다.

2. 누적합 풀이는 아래의 링크를 참고하면 좋을 것 같다.
   10025 누적합 풀이

3. 슬라이딩 윈도우로 문제를 풀이하기 위해서 얼음양동이들이 놓여질 배열을 만들어준다.
   1,000,000 개의 배열을 만들어두고, N개의 얼음양동이를 X의 위치에 G를 저장한다.

4. (3)번을 진행하면서, 불필요한 연산을 줄이기 위해 양동이가 놓여진 맨 나중 좌표를 구한다.

4. 현재 위치로부터 좌우로 K 만큼 닿을 수 있기 때문에 0 좌표를 기준으로 식 다음 위치를 계산하면 아래와 같다.
   p = k * 2 + 1

5. 얼음들의 최대값을 저장할 res 의 초기값은 0~p 까지의 값이고, (3)에서 구한 맨 나중 좌표까지 순회하면서 res의 값을
   갱신해주면 된다.

🖥 소스 코드

from sys import stdin

n, k = map(int, stdin.readline().split())
length, ans = 0, 0
arr = [0 for _ in range(10000001)]

for _ in range(n):
    g, x = map(int, stdin.readline().split())
    length = max(length, x)
    arr[x] = g

p = k * 2 + 1
res = sum(arr[:p])
ans = res

for i in range(p, length + 1):
    # 여기 p 값 안넣고 수식 넣을 떄 괄호 안 넣어서 틀렸음
    res += (arr[i] - arr[i - p])
    ans = max(ans, res)

print(ans)