뚝딱뚝딱

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

💡 수열

• 이 문제는 무지성으로 풀이하면 [시간초과]가 당연히 발생하는 문제이다.
• 입력 크기가 최대 10^6이므로 O(n^2)으로 풀 시 시간초과가 발생한다.
• 결론적으로 이 문제는 "누적합"="부분합"을 이용하여 풀이할 수 있다.
• 누적합을 저장할 크기가 N+1인 벡터를 생성하고, 0으로 초기화한다.
• N+1개를 생성한이유는 0번 인덱스를 0으로써 활용하기 위함이다.
• 누적합 배열을 v라고 할 때, 만약 K=2이면 v[2]-v[0]은 두번째 값까지 더한 값에서 0번째 값까지 더한 값을 빼준 것이고, 이 값은 첫번째값과 두번째값을 더한 것이므로, 단순히 빼기를 통해 구간의 합을 구할 수 있고, 이로써 중복적인 더하기 연산을 피할 수 있으므로 시간을 단축할 수 있다.
• 예시
  
  

• 주어진 예시에서 5개만을 가져와 보았다.
• 주어진 5개의 숫자값들이 위의 배열과 같을 때, 아래 v배열은 각 값들의 누적합을 차례로 1번 인덱스부터 채워넣는다.
• 하나씩 살펴보면, v[1]에는 첫번째 값인 3을, v[2]에는 두번째값까지 더한 값(3+(-2))인 1을, v[3]에는 세번째값까지 더한...
• 이제 K가 2이므로, 연속한 두 값씩 더한 값을 구해보자. 이는 이미 구해둔 v[K]-v[0] 연산만을 통해 구할 수 있다.
• 첫번째 연속합을 max로 지정해주고, for문을 통해 K+1부터 N까지 진행하면 된다.
• 이 방법은, cin으로 숫자값들을 받을 때, 동시에 배열에도 누적합을 더해 놨기 때문에, 이 값을 이용해 차 연산만 해주고, 그 연산 결과가 가장 큰 값을 반환하면 되므로, 시간효율이 아주 좋다! 

• 아래는 전체 코드이다.

#include<iostream>
#include<vector>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N,K;
    cin>>N>>K;
    
    vector<int> v(N+1,0);
    
    for(int i=1; i<N+1; i++){
        int temp;
        cin>>temp;
        v[i]=v[i-1]+temp;
    }
    
    int max=v[K];
    for(int i=K+1; i<N+1; i++){
        max=(max<v[i]-v[i-K])?v[i]-v[i-K]:max;
    }
    
    cout<<max;
    
    return 0;
}

이전에 유사한 누적합 문제를 풀어봐서 문제를 보자마자 바로 "누적합!!!"하며 풀 수 있었다.

코딩테스트를 준비하면서 여러 문제를 풀다보니, 점점 문제의 유형이 눈에 보이기 시작한 것 같다.

그래도 아직 갈길이 멀다...!!!