백준 21921 블로그 C++

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

21921번: 블로그

---

문제

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

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

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

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

---

입력

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

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

---

출력

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

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

---

해결방안 -> 최대방문자를 max라고 하고 서브배열을 sum으로 두면 처음에는 0~X동안 루프를 돌면서 합을 구하고 이 값을 max에 넣어둔다. 기간의 개수는 length라 두고 처음 값은 1

그 후 i = X ~ i~N까지 루프를 돌면서 서브배열의 합이 max보다 크다면 서브배열의 합을 max로 바꿔주고 기간의 개수인 length를 1로 초기화 해준다.

 

만약 max == sum이라면 기간의 개수 length를 1 증가시켜준다.

---

전체 소스 코드 ->

#include <iostream>

 

//백준 21921 블로그 (슬라이딩 윈도우)

 

using namespace std;

 

int main(void){

    long long arr[250000];

    int n,k;

    cin >> n >> k;

    for(int i = 0;i<n;i++){

        cin >> arr[i];

    }

    long long sum = 0;

    long long max_length = 0;

    long long max = 0;

   

    for(int i = 0;i<k;i++){

        sum = sum + arr[i];

    }

    max = sum;

    max_length = 1;

   

    for(int i = k;i<n;i++){

        sum = sum + arr[i];

        sum = sum - arr[i-k];

        if(sum > max){

            max = sum;

            max_length = 1;

        }

        else if(sum == max){

            max_length++;

        }

    }

   

   if(max != 0){

   cout << max << '\n';

   cout << max_length << '\n';

   }

    else if(max == 0){

        cout << "SAD" << '\n';

    }

}