백준 2559 수열(C++)

* 해당 문제 풀이는 '큰돌'님의 문제풀이에서 제가 이해한 부분을 재작성한것입니다

백준 2559 수열입니다

문제 해석

해당 문제는 문제 지문이 어렵지는 않았는데 해당 문제를 풀기 위한 개념(누적합)을 이해하는게 조금 어려웠습니다

우선 문제에서는 아래와 같이 n일 간에 온도가 주어졌을때 연속적인 k간의 온도의 합중 가장 큰값을 구하는 문제입니다

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

 

해당 문제를 풀기전에 누적합의 개념부터 알아보도록하겠습니다

누적합

부분합, 누적합이라고도 하며, 배열의 일부 구간에 대한 합을 빠르게 구할수 있는 방법입니다

예를 들어오면 [5,6,2,6,4] 와 같은 배열이 있을때 이 배열의 누적합을구하게 되면 아래와 같이 나오게 됩니다

5 11 13 19 23

즉 5 + 6한 결과에 2를 더하고 2를 더한 결과에 다시 6을 더하듯이 구간별로 값을 누적시키는 방법입니다

 

보통 누적합은 수열이 주어지고 어떤 구간의 값의 합을 구할때 많이쓰입니다

예를 들어 [5,6,2,6,4] 배열에서 인덱스 2번(a)부터 ~ 4번(b)까지의 구간합을 구해야 될경우(2,6,4)

arr[0~b까지의 누적합] - arr[0~a-1까지의 누적합]을 하게 된 인덱스2번 ~ 4번까지의 구간합이 나오게 됩니다

 

즉 arr[0~4의 누적합] = 23, arr[0~1] = 11, 23 - 11 = 12 가 나오게 되고 수기로 2 + 6 + 4를 하게되면 12가 나오는것을 알수있습니다

 

그러면 위에 문제 같은경우는 k를 기준으로 해서 [0~k의누적합] - [0~(i-k)의 누적합]의 최대값을 구하면 되는 문제입니다

 

또한 이문제같은경우는 최대값을 구하라고 나왔는데 최대값을 구하는 문제에서는 최솟값부터 정해야 되고, 최솟값을 구하는 문제에서는 최대값을 정하고 문제를 풀어야됩니다

이문제에 최솟값 같은경우는 n이 10만 까지 증가할수있고, 주어지는 온도는 -100이 최솟값입니다

그래서 10*-100을 하게되면 -10000000이 최솟값이 되는것입니다

 

문제 풀이 순서

1. 두개의 정수 N과,K선언 그리고 온도를 담을 temp 변수를 선업합니다

2. 누적합 배열 선언 및 최솟값 변수를 선언합니다

3. n 과 k 입력받습니다

4. n만큼 반복문을 돌면서 온도를 입력받고 입력받고 바로 다음 누적합을 계산해줍니다

5. 계산된 누적합을 k번째 부터 반복문을 돌려줍니다

6. [0~k의누적합] - [0~(i-k)의 누적합]공식대로 계산을 해주고 max함수를 사용하여 최대값을 갱신해줍니다

 

작성 코드

#include<bits/stdc++.h>
using namespace std;

//두개의정수 및,온도 temp,누적합,최솟값 변수 선언
int n,k,psum[100004],temp,ret=-10000004;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    //n과 k입력
    cin >> n >> k;

    //온도를 입력받으면서 누적합 구하기
    for(int i = 1; i < n; i++){
        cin >> temp;
        psum[i] = psum[i-1] + temp;
    }


    //계산된 누적합 배열을 k번째 부터 반복해줍니다
    for(int i = k; i <= n; i++){
        //[0~k의누적합] - [0~(i-k)의누적합]을 계산하고 최대값을 갱신합니다
        ret = max(ret,psum[i] - psum[i-k]);
    }
    cout << ret << "\n";
    

    return 0;
}

 

*누적합이 아직 이해가 될듯말듯하여 설명이 정확하지 않을수도있습니다.. 비슷한 유형에 문제를 계속 풀어야될꺼같습니다 ㅠㅠ