[구현 / BOJ 2559 / C++] 수열

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

2559번: 수열

1) psum이라는 누적합 배열을 만든다.
2) 누적합 배열을 이용해 각 K일씩의 합을 구한다.
3) 동시에, max 함수로 최대값을 구한다.

문제를 읽으면 이해하는 건 어렵지 않다. 하지만 이걸 그냥 문제 나온 그대로 코딩하면 

백퍼센트 오버플로우 혹은 타임 아웃이다.. 

 

이 문제는 누적합을 이용하는 문제이다.

psum[n]이라는 배열을 1일차부터 n일차까지의 합이라고 해보자,

그렇다면 psum[3] - psum[1] 은, 1~3일차까지의 합에서 1일차까지의 합을 뺀 값이다.

즉, 2일차 + 3일차를 의미한다.

 

따라서 psum[n+K] - psum[n] 은, n+1일차부터 n+K일차까지의 합을 의미한다.

이를 이용해서 문제를 해결하면 주어진 시간안에 해결할 수 있다.

 

추가로 max 함수를 이용하면 좀더 쉽게 해결할 수 있다.

(초기 mx값이 -1000001인 것은, -100(최저 온도) * 100,000(최대 관측일수) = -10000000 이 최솟값이기 때문이다.)

 

#include <bits/stdc++.h>

using namespace std;

int N, K, tmp, mx=-10000001;
int psum[100001];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> N >> K;
    for(int i = 1; i <= N ; i++){
        cin >> tmp;
        psum[i] = psum[i-1] + tmp;
    }
    
    for(int i = 0; i<=N-K ; i++){
        mx = max(mx, psum[i+K]-psum[i]);
    }
    cout << mx;
    
    
}