[Baekjoon/C++] 21921번 - 블로그

[백준] Baekjoon Online Judge

문제로 이동

 

문제

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

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

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

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

입력

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

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

출력

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

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

제한

•  1 ≤ X ≤ N ≤ 250,000
•  0 ≤ 방문자 수 ≤ 8,000

 

---

풀이

#include <iostream>
using namespace std;

int arr[250000];

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

    int N, X;
    cin >> N >> X;

    int result = 0, cnt = 0, sum = 0;

    for (int i = 0; i < N; i++) {
        cin >> arr[i];

        sum += arr[i];

        if (i >= X) sum -= arr[i - X];

        if (sum == result) cnt++;
        else if (sum > result) {
            result = sum;
            cnt = 1;
        }
    }

    // 출력
    if (result == 0) cout << "SAD\n";
    else cout << result << '\n' << cnt << '\n';

    return 0;
}

 

    int result = 0, cnt = 0, sum = 0;

    for (int i = 0; i < N; i++) {
        cin >> arr[i];

        sum += arr[i];

        if (i >= X) sum -= arr[i - X];

        if (sum == result) cnt++;
        else if (sum > result) {
            result = sum;
            cnt = 1;
        }
    }

문제의 답을 구하는 코드이다. i가 X 이상이 된다면 X일 이상의 방문자 수가 더해진 것이므로 sum에서 가장 먼저 더했던 수부터 하나씩 빼준다. 이렇게 구한 수 sum을 result와 비교해서 더 큰 것을 result에 저장하고, result와 값이 같은 sum의 등장횟수 cnt를 갱신한다.