10025 - 게으른 백곰

문제

https://www.acmicpc.net/problem/10025

느낀점

투 포인터 문제의 경우, 브루트포스와 같은 O(N*2)를 피하기위해 하나의 반복문만 사용한다. 그리고 인덱스가 진행됨에따라 문제의 정답을 하나씩 빼고 더하게 되는데 그것을 적용할 수 있는 부분을 문제에서 잘 찾는 게 중요하다.

풀이

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define pii pair<int, int>

int main()
{
    int N, K;
    int maxCoord = -1;
    cin >> N >> K;
    vector<int> iceList(1000001, 0);
    for (int i = 0; i < N; i++)
    {
        int ice, coord;
        cin >> ice >> coord;
        maxCoord = max(coord, maxCoord);
        iceList[coord] = ice;
    }
    long initAnswer = 0;
    for (int i = 0; i <= 2 * K; i++)
    {
        if (i > maxCoord)
        {
            break;
        }

        initAnswer += iceList[i];
    }

    int left = 0;
    long answer = initAnswer;
    for (int right = 2 * K + 1; right <= maxCoord; right++)
    {
        initAnswer += iceList[right];
        initAnswer -= iceList[left];
        answer = max(answer, initAnswer);
        left++;
    }
    cout << answer;

    return 0;
}