[백준 10025번] 게으른 백곰 (C++)

문제링크 : https://www.acmicpc.net/problem/10025

10025번: 게으른 백곰

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

int arr[1000001];

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N, K, g, x;
    cin >> N >> K;

    for(int i=0; i<N; i++)
    {
        cin >> g >> x;
        arr[x] = g;  //위치에 따른 값 할당
    }

    int sum = 0;
    int result = 0;

    for(int i=0; i<=1000000; i++)
    {
        sum+=arr[i];
        if(i>=K*2+1)  //좌우 K만큼이기에 총 길이는 K*2+1
        {
            sum-=arr[i-(K*2+1)]; //맨 앞에 값을 빼줌
        }
        result = max(result, sum);
    }

    cout << result;

    return 0;
}

탐색하는 범위는 좌우로 K만큼이다.

따라서 탐색하는 총 범위의 길이는 K*2 + 1(자기자신)인 것을 알 수 있다.

 

처음부터 차례로 더해나가다가, 더해나간 길이가 K*2+1보다 커질때 맨 앞에 값을 더했던 sum에서 빼줌으로써 범위를 조정한다.

여기서 i=0부터 시작했기에 K*2+1보다 같을때도 이와 같은 작업을 수행한다.

이렇게 뒤에 하나 더하고, 앞에 하나 빼주면서 반복하며 가장 큰 값을 저장하여 출력한다.