백준(BOJ) 21921 블로그 C++ 풀이

문제 링크: https://www.acmicpc.net/problem/21921

21921번: 블로그

풀이에 이용된 알고리즘: 구간합, 누적합

 

고정된 길이 x의 구간 내 원소의 합이 가장 큰 구간을 찾고 그 합을 출력하는 문제이다.

 

또한 서로 다른 구간일지라도 동일한 합을 보이는 경우, 그 합이 등장한 횟수를 증가시켜가며 최종적으로 횟수 또한 출력한다.

 

for문 사용하여 어떤 원소들의 합을 구하면 되고, 해당 구간을 한칸씩 이동시켜나가면서 그 합의 maximum 값을 찾으면 되겠네?

 

라고 생각하고 직접 풀어보지는 않았지만 스마트한 느낌은 없어서 조금 다른 풀이를 해보았다.

 

어떤 합을 구할 때 매번 해당 구간을 O(n)으로 순회하면 비효율적이므로, 구간을 1만큼 우측으로 이동해나갈 때

"(이전의 구간합) - (이전 구간의 첫 원소) + (현재 구간의 마지막 원소)" 라는 식을 이용하면 단 두번의 연산으로 늘 새로운 구간합을 빠르게 계산할 수 있다.

 

물론 가장 처음의 구간에 대해서는 O(n)의 순회를 통해서 구간합 sum을 구하여야 한다.

 

ex. ..... 3 1 5 23 21 8 20... <-- 이런 시퀀스에서 구간 길이 3의 구간을 살펴볼 때, (1 5 23)의 구간합은 29이다. 그리고 바로 옆에서 등장하는 구간 (5 23 21)의 구간합은 29 - 1 + 21 = 49이다.

 

/* BOJ 21921 블로그 */
#include <iostream>
#include <functional>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <string.h>
#include <vector>
 
using namespace std;
 
#define endl '\n'
 
typedef long long ll;
 
int n, x, arr[250001];
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    //freopen("input.txt", "r", stdin);
 
    cin >> n >> x;
    for (int i = 1; i <= n; i++)
        cin >> arr[i];
 
    int ans = 0;
    int ans_cnt = 0;
 
    int sum = 0;
    for (int i = 1; i <= n - x + 1; i++)
    {
        if (i == 1) // 가장 처음에는 o(n)으로 구간합 계산하기
        {
            for (int idx = i; idx <= i + x - 1; idx++)
                sum += arr[idx];
            ans = sum;
            ans_cnt = 1;
        }
        else
        {
            // 새로운 구간 합이 현재까지 등장한 maximum 구간합 보다 큰 경우
            if (ans < sum - arr[i - 1] + arr[i + x - 1])
            {
                ans_cnt = 1;                             // 해당 합의 등장 횟수를 1로 초기화
                ans = sum - arr[i - 1] + arr[i + x - 1]; // maximum 구간합 갱신
            }
            // 새로운 구간 합이 현재까지 등장한 maximum 구간합과 동일한 경우
            else if (ans == sum - arr[i - 1] + arr[i + x - 1])
                ans_cnt++; // maximum 구간합 등장 횟수 1회 증가
 
            sum = sum - arr[i - 1] + arr[i + x - 1]; // 변경된 구간합으로 sum 갱신
        }
    }
 
    if (ans == 0)
        cout << "SAD" << endl;
    else
    {
        cout << ans << endl;
        cout << ans_cnt << endl;
    }
 
    return 0;
}