백준/실버
[백준 10025번] 게으른 백곰 (C++)
게임개발기원
2023. 4. 8. 16:49
문제링크 : https://www.acmicpc.net/problem/10025
10025번: 게으른 백곰
첫 줄에 정수 N과 K가 들어온다. 둘째 줄부터 N째 줄까지, 공백을 사이에 두고 각 양동이의 얼음의 양을 나타내는 gi와 양동이의 좌표를 나타내는 xi가 주어진다.
www.acmicpc.net
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>
int arr[1000001];
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int N, K, g, x;
cin >> N >> K;
for(int i=0; i<N; i++)
{
cin >> g >> x;
arr[x] = g; //위치에 따른 값 할당
}
int sum = 0;
int result = 0;
for(int i=0; i<=1000000; i++)
{
sum+=arr[i];
if(i>=K*2+1) //좌우 K만큼이기에 총 길이는 K*2+1
{
sum-=arr[i-(K*2+1)]; //맨 앞에 값을 빼줌
}
result = max(result, sum);
}
cout << result;
return 0;
}
탐색하는 범위는 좌우로 K만큼이다.
따라서 탐색하는 총 범위의 길이는 K*2 + 1(자기자신)인 것을 알 수 있다.
처음부터 차례로 더해나가다가, 더해나간 길이가 K*2+1보다 커질때 맨 앞에 값을 더했던 sum에서 빼줌으로써 범위를 조정한다.
여기서 i=0부터 시작했기에 K*2+1보다 같을때도 이와 같은 작업을 수행한다.
이렇게 뒤에 하나 더하고, 앞에 하나 빼주면서 반복하며 가장 큰 값을 저장하여 출력한다.