[백준] 10025 게으른 백곰

백준: 문제

10025번: 게으른 백곰

오늘 아예 작정하고 슬라이딩 윈도우 문제를 풀고 있다. 이전 두 문제는 별도의 배열을 사용해 조금 어렵게 접근했어야 했던 문제라면 이번 문제는 풀이 방식은 쉬우나 배열 처리가 어려운 문제였다. 왜냐하면 우선 전체 배열 크기를 문제에서 제시하지 않고 주어진 수의 범위를 통해 계산해야했기 때문이다. 여기서 K의 범위가 0이상 2,000,000이므로 전체 배열의 크기는 2,000,000 * 2 + 1이다.

이제 주어진 양동이를 알맞게 위치시키고, 앨버트를 한칸씩 옮기면서 2 * K + 1 크기의 윈도우도 같이 앨버트의 좌측에서 우측으로 하나씩 옮긴다.

앨버트의 범위가 곧 슬라이딩 윈도우!

이를 전체 범위에서 한칸씩 옮기나 전체 배열의 크기가 워낙 크기 때문에 최소한의 이동만을 하도록 설정하였다. 바로 입력된 x 중 가장 큰 maxidx를 설정한 뒤, 슬라이딩 윈도우의 오른쪽 끝이 maxidx에 닿으면 탐색이 끝이나도록 설정하였다. 왜냐하면 이보다 더 오른쪽으로 가면 전체 얼음의 양이 줄어들기는 해도, 늘어날 수는 없기 때문이다. 이를 위해 섬세한 인덱스 처리가 중요했다. 아무래도 값이 커서 계산하기 어려운데, 그 때는 직접 예시로 두어개 넣어보면 금방 계산해낼 수 있다.

#include <iostream>
#include <algorithm>
using namespace std;
int arr[4000001];
int main(void){
    int n, k;
    long long sum = 0, mx;
    int g, x, maxidx = 0;
    cin >> n >> k;
    for(int i = 0;i < n;i++){
        cin >> g >> x;
        maxidx = max(maxidx, x);
        arr[x] = g;
    }
    for(int i = 0;i <= 2 * k;i++){
        sum += arr[i];
    }
    mx = sum;
    // 윈도우의 제일 왼쪽 arr[i] 값을 버리고 새로운 arr[i + 2 * k + 1]의 값을 더해서 윈도우의 크기 유지
    for(int i = 0; i < maxidx - 2 * k;i++){
        sum -= arr[i];
        sum += arr[i + 2 * k + 1];
        mx = max(mx, sum);
    }
    cout << mx;
}