[21921] 블로그(C++)

문제

찬솔이는 블로그를 시작한 지 벌써 $N$일이 지났다.

요즘 바빠서 관리를 못 했다가 방문 기록을 봤더니 벌써 누적 방문 수가 6만을 넘었다.

찬솔이는 $X$일 동안 가장 많이 들어온 방문자 수와 그 기간들을 알고 싶다.

찬솔이를 대신해서 $X$일 동안 가장 많이 들어온 방문자 수와 기간이 몇 개 있는지 구해주자.

 

 

입력

첫째 줄에 블로그를 시작하고 지난 일수 $N$와 $X$가 공백으로 구분되어 주어진다.

둘째 줄에는 블로그 시작 $1$일차부터 $N$일차까지 하루 방문자 수가 공백으로 구분되어 주어진다.

 

 

출력

첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다.

만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다.

 

 

해결 방법

전형적인 슬라이딩 윈도우 문제이다. 

초기 윈도우를 1일차 ~ X일차까지의 방문자 수의 총합으로 설정한뒤,

이 윈도우를 한 칸씩 오른쪽으로 옮기면서 최대 방문자 수를 갱신하면 된다.

즉, 초기 윈도우 값에서 매번 [i-1]일차의 방문자 수를 빼고 [i + x - 1]일차의 방문자 수를 더해주면 된다.

슬라이딩 윈도우 문제는 직접 그림을 그려보면 인덱스의 변화를 쉽고 빠르게 확인할 수 있으니 잘 이해가 안된다면 그림을 그려보는 것을 추천!

 

 

내 코드

// [21921] 블로그
#include <iostream>
using namespace std;

int n, x, visitors[250001];

void input()
{
    cin >> n >> x;
    for(int i = 1; i <= n; i++) {
        cin >> visitors[i];
    }
}

void findMaxVisitors()
{
    int maxDays = 1;
    long long sum = 0, maxVisitors = 0;

    for(int i = 1; i <= x; i++) {
        sum += visitors[i];
    }
    maxVisitors = sum;
    for(int i = 2; i <= n - x + 1; i++) {
        sum = sum - visitors[i - 1] + visitors[i + x - 1];
        if(sum > maxVisitors) {
            maxVisitors = sum;
            maxDays = 1;
        }
        else if(sum == maxVisitors) {
            maxDays++;
        }
    }
    if(maxVisitors == 0) cout << "SAD\n";
    else {
        cout << maxVisitors << '\n';
        cout << maxDays << '\n';
    }
}

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

    input();
    findMaxVisitors();

    return 0;
}