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

누적합을 이용하면 쉽게 풀 수 있는 문제다.

sum[i]을 0~i까지의 인덱스의 모든 값의 합이라고 정의하면

for문을 돌면서 sum[i] - sum[i - x]를 구하면 x일의 모든 방문수를 확인할 수 있다.

 

---

정답 코드

#include <iostream>

using namespace std;

int n, x, arr[250000];
int sum[250000], Max, cnt;

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

    //input
    cin >> n >> x;
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    //add
    sum[0] = arr[0];
    for (int i = 1; i < n; i++)
        sum[i] = sum[i - 1] + arr[i];

    //search
    Max = sum[x - 1];
    cnt = 1;
    for (int i = x; i < n; i++){
        int temp = sum[i] - sum[i - x];

        if (temp > Max){
            Max = temp;
            cnt = 1;
        }
        else if (temp == Max)
            cnt++;
    }

    //output
    if (Max == 0)
        cout << "SAD\n";
    else
        cout << Max << "\n" << cnt << "\n";
}