백준 21921 - 블로그

문제 설명

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

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

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, X일 동안 최다 방문자 수를 구하는 것이다.

또한, 최다 방문자 수의 구간의 개수도 같이 구해야 한다.

 

해당 문제는 누적합을 이용하면 간단하게 해결할 수 있다.

누적합을 이용하면 i일부터 i+X-1일까지의 합을 $O(1)$시간 안에 구할 수 있다.

예를 들어, 2일 부터 3일까지의 누적합을 계산하는 경우를 봐보자.

2~3일의 방문자 수는 6이 된다.

이는 3일의 누적합에서 1일의 누적합을 뺀 것과 같다.$7-1 = 6$

 

즉, 입력을 받는 과정에서 누적합을 계산한 뒤 최다 방문자 수를 배열의 범위 내에서 구하면 된다.

 

 

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>

using namespace std;

int N, X;


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

    cin >> N >> X;

    vector<int> sum(N, 0);
    for (int i = 0; i < N; i++)
    {
        int num;
        cin >> num;

        if (i == 0) sum[i] = num;
        else sum[i] += sum[i - 1] + num;
    }

    pair<int, int> ans = { sum[X-1], 1 };
    for (int i = 1; i <= N - X; i++)
    {
        int total = sum[i + X - 1] - sum[i - 1];
        if (ans.first == total)
        {
            ans.second++;
            continue;
        }
        else if (ans.first < total)
        {
            ans.first = total;
            ans.second = 1;
        }
    }

    if (ans.first == 0) cout << "SAD";
    else cout << ans.first << "\n" << ans.second;

    return 0;
}

---