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

백준 10025 게으른 백곰

1. 문제

문제 링크

2. 접근법

[ 문제 접근 ]

 

백곰 앨버트가 1차원 배열로 이루어진 우리 안에 자리를 잡고 좌, 우로 k만큼 떨어진 양동이에 닿을 수 있다.

여기서 앨버트를 기준으로 좌, 우로 k만큼 닿는 거리와 (앨버트의 위치에 해당하는 인덱스 - k)에서 (k*2)+1까지의 거리는 같다. 따라서 위의 거리를 기준으로 부분합을 구해서 최댓값을 출력하면 된다.

 

이때 for문을 돌리면서 i를 증가시키는데 i가 (k*2)+1 보다 크면 구한 합에서 i-(k*2)+1 의 인덱스에 해당하는 얼음의 양을 빼준다. 또한 x 좌표의 최댓값은 100만 이므로 100만 번 수행해준다.

3. 코드

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int map[1000001];

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

	int n, k, g, x, ans=0, sum=0;
	cin >> n >> k;

	for (int i = 0; i < n; ++i)
	{
		cin >> g >> x;
		map[x] = g;
	}
	//기준점 생성
	int val = (k * 2) + 1;
	for (int i = 0; i <= 1000000; ++i)
	{
		//i가 val보다 크면 구한 합에서 i-val의 인덱스를 빼줌
		if (i >= val)
			sum -= map[i - val];
		//부분합 구하기
		sum += map[i];
		//최댓값 갱신
		ans = sum > ans ? sum : ans;
	}
	cout << ans << "\n";
	return 0;
}

4. 시간 복잡도

최대 100만번 수행한다.

5. 결과