[백준 C++] 21921번 : 블로그

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

21921번: 블로그

풀이 :
- 11441번 문제에서 응용된 문제
- 주어진 x가 j가 되고, i는 j-x가 되는 것.
- 구간합에서 가장 큰 값을 구하되, 가장 큰 값이 여러 개일 경우 갯수를 세어준다
- 가장 큰 값이 0일 경우 SAD를 출력하고, 그렇지 않다면 가장 큰 값과 갯수를 출력한다
 
코드 :

#include <iostream>
#include <algorithm>
using namespace std;

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

    int n, x, num, sum[250005] = {0, }, max, cnt;

    cin >> n >> x;
    max = cnt = 0;
    for(int i=1; i<=n; i++){
        cin >> num;
        sum[i] = sum[i-1] + num; //누적합 배열 만들기
    }
    for(int i=x; i<=n; i++){ //i는 x에서부터 시작
        if(sum[i]-sum[i-x] > max){ //x일만큼의 구간합이 더 클 경우
            max = sum[i]-sum[i-x]; //max를 갱신하고
            cnt = 1; //cnt를 초기화해준다
        }else if(sum[i]-sum[i-x] == max){ //max값과 같을 경우
            cnt++; //갯수를 더해준다
        }
    }
    if(max == 0){
        cout << "SAD\n";
    }else{
        cout << max << '\n' << cnt << '\n';
    }
}