[BOJ/C++] 블로그(21921번)

1. 개요

https://www.acmicpc.net/problem/21921

21921번: 블로그

1-1. 설명

찬솔이는 블로그를 시작한지 N일이 지났다. 요즘 바빠서 관리를 못했다가 방문 기록이 6만을 넘겼다. 찬솔이는 X일 동안 가장 많이 들어온 방문자 수와 그 기간을 알고싶다. X일동안 가장 많이 들어온 방문자 수와 기간이 몇개 있는지 구하는 프로그램을 구현한다.

1-2. 제한 사항

 - 첫 줄에는 블로그를 시작하고 지난 일수 N과 X가 주어짐

 - 둘째 줄부터는 블로그 시작 1일차부터 N일차까지 하루 방문자 수가 주어짐

---

2. 구현

2-1. 풀이

단순하게 이중 for문을 하면 시간초과가 날 것을 예상하여, 다른 방법을 찾아보았다. 누적합을 통해 풀이를 진행하면 시간초과가 나지 않으므로 누적합으로 구현해보았다. 

2-2. 코드

#include <iostream>
using namespace std;

constexpr size_t MAX_NUM = 250001;
int days[MAX_NUM];

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

    int N, X, maxNum, count = 1;
    cin >> N >> X;
    for (int i = 1; i <= N; i++) {
        cin >> days[i];
        days[i] = days[i - 1] + days[i];
    }

    maxNum = days[X];
    for (int i = 1; i <= N - X; i++) {
        int curNum = days[i + X] - days[i];
        if (maxNum < curNum) {
            maxNum = curNum;
            count = 1;
        }
        else if (maxNum == curNum) count += 1;
    }

    if (maxNum == 0) cout << "SAD";
    else cout << maxNum << "\n" << count;

    return 0;
}