[BOJ/C++] 10025 게으른_백곰(누적합, 슬라이딩 윈도우)

처음에는 이 문제를  누적합과 투포인터를 사용해서 풀었다.

#include<iostream>
using namespace std;
int main(){
    int n, k, g, point;
    cin >> n >> k;
    int st=0, end = k-1, mx=0, mxp =0;

    int x[1000001] = {0};
    int sum[1000001] = {0};
    for(int i=0; i<n; i++){
        cin >> g >> point;
        x[point] = g;
        if(mxp < point){
            mxp = point;
        }
    }

    // 누적합 구하기
    for(int i=0; i<=mxp; i++){
        if(i==0) sum[i] = x[i];
        else sum[i] = sum[i-1] + x[i];
    }
    // cout << mxp <<"\n";
    // for(int i=0; i<=mxp; i++){
    //     cout << i  << " " << sum[i] <<"\n";
    // } 

    if(mxp < k){
        mx = sum[mxp];
    }

    while(end<=mxp){
        if(end-st>k*2){
            st ++;
        }
        //cout << st << " " << end << " " <<  sum[end]-sum[st-1] << "\n";
        if(sum[end]-sum[st-1]> mx){
            mx = sum[end]-sum[st-1];
        }
        end ++;
    }

    cout << mx <<"\n";

    



}

 

메모리: 죽을게

시간: 간당간당할게

 

문제점

1. 얼음 위치 배열과 누적합 배열 2개를 사용해 메모리 2배 사용

2. 누적합 생성, 탐색시 배열을 한번씩 순회 (총 2번 순회)

 

개선방법 : 슬라이딩 윈도우

1. 얼음 위치 배열만 사용하여 윈도우에 벗어나면 sum에서 빼주기

2. 탐색시에만 배열 순회 (총 1번 순회)

 

슬라이딩 윈도우란 배열이나 문자열 같은 연속된 데이터에서 고정된 크기의 창을 이동시키면서 그 안의 요소들로 특정 조건(합, 최대/최소값, 부분 문자열 등)을 효율적으로 해결하는 기법입니다. 이는 전체를 다시 계산하는 대신 창이 한 칸씩 움직일 때 양 끝의 원소만 갱신하여 중복 계산을 피하고 시간 복잡도를 O(M)으로 줄인다.

 

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    ios_base :: sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);

    int n, k, g, x;
    cin >> n >> k;
    int mxp = 0;
    int bucket[1000001] = {0};

    for(int i=0; i<n; i++){
        cin >> g >> x;
        bucket[x] = g;
        mxp = max(mxp, x);
    }   

    int sum = 0, mx = 0;
    int w_size = 2*k+1;

    for(int i=0; i<=mxp; i++){
        sum += bucket[i];
        if(i>=w_size)
            sum -= bucket[i-w_size];
        mx = max(mx, sum);
        //cout << i << " " << sum << " " << mx << "\n";

    }

    cout << mx <<"\n";


}