[백준 2559] 수열

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

 

많은 깨달음을 주는 문제였다.

수열이 주어졌을 때, K(연속되는 수)의 합 중 가장 큰 값을 리턴해달라는 문제다.

 

N(수열의 개수) : 1 ~ 10만

K는 1과 N 사이의 정수이므로 최대는 10만 정도

 

단순하게 생각하면 10^10만이라 시간 안에 문제를 해결할 수 없다.

어떤 연속된 수의 합을 빠르게 구할 수 있는 방법은 누적합(prefix sum)을 이용하는 것이다.

 

누적합은 0 ~ k 구간의 합을 미리 차곡차곡 더해서 저장해 둔다.

 

문제의 예시를 보면

10 5

3 -2 -4 -9 0 3 7 13 8 -3

5개의 연속된 수열의 최댓값은 31이다.

 

각각의 누적합을 구해보면

1까지의 누적합은 0 + 3

2까지의 누적합은 0 + 3 - 2

3까지의 누적합은 0 + 3 -2 - 4

가만히 보면 3까지의 누적합은 2까지의 누적합 + 입력된 숫자다.

입력을 받을 때 누적합의 배열도 같이 채워나가면 된다.

 

-9 0 3 7 13의 구간 합을 알고 싶다면?

[13까지의 누적합] - [-4까지의 누적합]이다.

[13까지의 누적합] = 3 -2 -4 -9 0 3 7 13

[-4까지의 누적합] = 3 -2 -4

[구하려고 하는 것] = -9 0 3 7 13

 

누적합을 미리 정해놓고 가져다 쓰는 건 랜덤 접근이므로 O(1)

K는 최대 10만

10만 x O(1) => 시간 안에 해결이 가능하다.

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

int n, k, num, sum, ans = -10000004;
int arr[100005];
int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> num;
        arr[i] = arr[i - 1] + num;
    }
    
    for (int i = k; i <= n; i++)
    {
        ans = max(ans, arr[i] - arr[i - k]);
    }
    
    cout << ans << '\n';
    return 0;
}