C++ / 백준 / 10025 / 게으른 백곰

문제

 

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

10025번: 게으른 백곰

문제풀이

 

처음에는 이중 반복문으로 풀었는데 시간 초과가 나서  투 포인터를 이용해 풀었다.

 

pair<int, int>를 이용해 벡터에 앞부분에는 좌표, 뒷부분에는 얼음양을 입력받는다.

백곰은 한번 정한 자리에서 -K ~ +K 부분까지만 이동할 수 있다.

입력은 좌표순이 아니므로 sort함수를 이용해 좌표를 오름차순으로 정렬한다.

 

먼저 left, right를 0으로 정한 뒤 left, right를 움직이며 범위를 정한다.

만약 left ~ right의 범위가 2 * K이하라면 누적합을 구하는 sum변수에 right부분에 해당하는 얼음양을 더한다.

만약 left ~ right의 범위가 2 * K초과라면 누적합을 구하는 sum변수에  left부분에 해당하는 얼음양을 뺀다.

이렇게 left와 right를 한 칸씩 움직이면서 범위가 2 * K안에 들어가는지, 들어간다면 누적합, 들어가지 않는다면 값을 빼어 최대 값을 구하면 된다.

 

 

코드

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N(0), K(0);
	cin >> N >> K;
	vector<pii>bucket(N);

	for(int idx=0;idx<N;++idx) cin>> bucket[idx].second >> bucket[idx].first;

	sort(bucket.begin(), bucket.end());
	
	int answer(0);
	
	int left(0), right(0), sum(0);
	while (1) {
		if (right == N) break;		
		if (bucket[right].first - bucket[left].first <= 2 * K) {
			sum += bucket[right++].second;
		}
		else if (bucket[right].first - bucket[left].first > 2 * K) {
			sum -= bucket[left++].second;
		}		
		answer = max(answer, sum);
	}
	
	cout << answer;
}