[백준 C++] 2559번 : 수열

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

2559번: 수열

풀이 :

- n길이의 수열에서 k구간의 합 중 최대값을 구하는 문제이다

- 구간의 합을 구하는 문제는 누적합을 이용하면 쉽게 구할 수 있다

- 첫번째 예제를 생각해보자

이렇게 누적합이 구해진다.

1~2 구간 : sum[2] - sum[0] 

2~3 구간 : sum[3] - sum[1]

다른 구간도 마찬가지이다.

따라서 i = k일 때, sum[i] - sum[i-k]로 구할 수 있다.

하지만, 제일 처음 구간 즉, 0~1구간을 같은 공식으로 구하면 i가 1일때 -1을 참조하게 된다.

그것을 막기 위해 ans의 초기화는 sum[k-1]로 해주고 i는 k부터 시작하게 해줬다.

k-1인 이유는 0부터 시작하기 때문

 

코드 :

#include <iostream>
#include <stdlib.h>

using namespace std;

int main(){
    int n, k, arr[100005], sum[100005], ans;

    cin >> n >> k;
    for(int i=0; i<n; i++){ // 입력과 동시에 누적합을 구해서 배열에 넣어줄 것
        cin >> arr[i];
        if(i == 0){ // 누적합의 0번째 배열에는 0번째 인덱스에 들어있는 값 그 자체이고, 
            sum[i] = arr[i]; // sum[-1] 방지를 위해 따로 처리
        }else{
            sum[i] = sum[i-1] + arr[i]; // 인덱스가 0이 아닐 경우 누적합 배열 직전 인덱스와 들어온 값을 더해 누적합을 구한다
        }
    }
    ans = sum[k-1]; 
    for(int i=k; i<n; i++){ 
        ans = max(ans, sum[i]-sum[i-k]); // ans에 들어있는 값과 비교하여 최대값 갱신
    }
    cout << ans << '\n';
}