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

개요

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

10025번: 게으른 백곰

실버3 난이도 문제다.

풀이

백곰 앨버트가 가장 많은 얼음을 취할 수 있는 최적의 위치를 찾아야 한다.

 

브루트포스로 접근해서 한 번 틀렸다.

생각해 보니 다 계산할 필요가 없었다.

현재 위치에서 취하는 얼음의 범위가 ice[n] ~ ice[m]라고 가정하자.

다음 범위는 ice[n+1] ~ ice[m+1]일 것이다.

다 계산할 필요 없이 현재 범위에서 -[n] + [m+1]만 해주면 된다.

이게 슬라이딩 윈도우였다.

코드

#include<iostream>
#include<algorithm>
using namespace std;
constexpr int LIMIT = 1000000;

int N, K;
int g, x;
int ice[LIMIT+2];
int ans, sum;

void TwoPointer()
{
	int head = 0;
	int tail = K * 2;
	if (tail > LIMIT)
	{
		for (const auto& i : ice)
			sum += i;

		ans = sum;
		return;
	}
	while (tail <= LIMIT)
	{
		sum = 0;
		for (int i = head; i <= tail; i++)
			sum += ice[i];

		ans = max(ans, sum);

		head++;
		tail++;
	}
}
int main()
{
	cin.tie(0)->sync_with_stdio(0);
	
	cin >> N >> K;

	for (int i = 0; i < N; i++)
	{
		cin >> g >> x;
		ice[x] = g;
	}

	TwoPointer();

	cout << ans;
}