[BOJ] 게으른 백곰 10025번 C++

 

 

문제

더운 여름날 동물원의 백곰 앨버트는 너무 더워서 꼼짝도 하기 싫다. 다행히도 사육사들이 앨버트의 더위를 식히기 위해 얼음이 담긴 양동이들을 가져다 주었다. 앨버트가 가장 적은 거리만 움직이고도 최대한 많은 얼음으로 더위를 식힐 수 있도록 도와주자.

우리 안은 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만큼 떨어진 거리 내에 있는 얼음들의 합(최댓값)을 출력한다.

 

접근 방식

 

엘버트는 좌우로 떨어진 양동이까지 닿을 수 있기 때문에

시작 점에서 끝점까지 최대 거리는 2*K가 된다

 

이를 이용해서 투 포인터를 이용한 슬라이딩 윈도우를 구현하면 된다.

즉, 두개의 포인터를 가지고 2*K이내의 거리라면 오른쪽 포인터를 증가시키면서 얼음들의 합의 최댓값을 찾는다

만약, 2*K 초과라면 왼쪽 포인터를 2*K 이내로 이동시키면서 지금까지 누적된 합에서 왼쪽 포인터의 얼음들을 빼면 된다

이러면 시간복잡도 O(N)에 해결할 수 있다(고 gpt가 그런다)!

 

 

코드

#include<bits/stdc++.h>
using namespace std;
int mat[1000003];
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int N, K; cin>>N>>K;
    vector<pair<int,int>> v;
    for(int i=0; i<N; i++) {
        int g,x; cin>>g>>x;
        v.push_back({x,g});
    }
    sort(v.begin(), v.end());

    int l=0,r=0, sum = 0, ans = 0;

    while(r < N) {
        sum += v[r].second;

        while(v[r].first - v[l].first > 2 * K) {
            sum -= v[l].second;
            l++;
        } 
        ans = max(ans, sum);
        r++;
    }
    cout<<ans;
}