[백준 21921번] 블로그 (C++)

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

21921번: 블로그

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

int arr[250001];
int arr_sum[250001];

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

    int N, X, sum = 0, maxV = 0;
    cin >> N >> X;

    for(int i=1; i<=N; i++)
    {
        cin >> arr[i];
        sum += arr[i];
        arr_sum[i] = sum; //누적합
    }

    int cnt = 1; //구간 최소 길이 1
    for(int i=X; i<=N; i++)
    {
        int sum_tmp = arr_sum[i] - arr_sum[i-X]; //각 구간 합
        if(maxV < sum_tmp) //최대 구간 갱신
        {
            maxV = sum_tmp;
            cnt = 1;
        }
        else if(maxV == sum_tmp) cnt++; //최대 구간 갯수 갱신
    }

    if(maxV==0) cout <<"SAD";
    else cout << maxV <<'\n' << cnt;

    return 0;
}

각 구간에 대한 누적합을 저장하고 시작한다.

X의 길이만큼의 누적 합들을 확인하는데, 최대 구간 합을 따로 저장하고, 최대 구간 합이 새롭게 나타난 것이라면 해당 구간 합의 갯수도 다시 카운팅해야 하므로 cnt = 1로 만든다.

이후 갱신했던 최대 구간 합과 똑같은 값이 나온다면 최대 구간 합의 갯수가 증가한 것이므로 cnt를 증가시켜준다.