[백준 12847번] 꿀 아르바이트 (C++)

문제링크 : https://www.acmicpc.net/problem/12847

12847번: 꿀 아르바이트

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int arr[100001];
ll result = 0, sum = 0;

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

    int N, M;
    cin >> N >> M;
    for(int i=0; i<N; i++)
    {
        cin >> arr[i];
    }

    for(int i=0; i<N; i++)
    {
        sum+=arr[i]; //누적합
        if(i>M-1) sum-=arr[i-M]; //앞에 값 빼주기
        result = max(result, sum); //최대값 저장
    }

    cout << result;
    
    return 0;
}

 

누적합을 이용한 문제이다.

처음에는 그냥 계속해서 더해주다가, (sum+=arr[i]]

현재 더해준 값의 갯수가 M을 넘어가면 넘어간 만큼 맨 앞부터 값을 빼주는 과정을 거친다. (sum-=arr[i-M])