[BOJ/21921] 블로그 , c++

🔗 링크

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

21921번: 블로그

https://github.com/jokj624/PS/blob/master/20000-25000/21921.cpp

jokj624/PS

🤯 한줄 후기

한줄 후기 : 제목에 이끌림

🤷 문제

👩‍💻 풀이

누적합 문제

블로그 올리려고 백준 들어갔다가 최근 올라온 문제에 '블로그' 문제가 있길래 귀여워서 들어갔다.

문제 읽어보니 처음에 덱인가? 하다가 누적합으로 풀면 금방 풀릴 것 같아서 시도했다.

 

매번 누적합을 저장할 배열에 바로 전 누적합과 현재 방문자 수를 더해준다.

원하는 기간이 X일 때, 현재 위치가 i 라면 (i > X) sum[i] - sum[i-X] 가 X기간 동안의 방문자 수가 된다.

이를 비교하여, 최대 일때를 갱신하고, 같은 값이 나온다면 카운팅 해주면 되는 문제이다.

💻 코드

//AC
//BOJ 21921 블로그 
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
ll sum[250001];
int main(){
    int N, X, num;
    cin >> N >> X;
    for(int i=0; i<N; i++){
        scanf("%d", &num);
        if(i==0)  {
            sum[i] = num;
            continue;
        }
        sum[i] = sum[i-1] + num;
    }
    ll maxSum = sum[X-1];
    int cnt = 1;
    for(int i=X; i<N; i++){
        if(maxSum < sum[i] - sum[i-X]){
            maxSum = sum[i]-sum[i-X];
            cnt = 1;
        }
        else if(maxSum == sum[i]-sum[i-X]){
            cnt += 1;
        }
    }
    if(maxSum == 0){
        printf("SAD");
    }
    else{
        printf("%lld\n", maxSum);
        printf("%d", cnt);
    }
}