백준, BOJ, 2096번, 내려가기 C++ [CPP] ★★★

우선 DP문제인줄 알고 풀었고

메모리도 적당히 딱 맞는듯해서 그렇게 풀었지만

의도는 다른 것이라고 한다.

 

슬라이딩 윈도우라고 하는데..?

음.. 투포인터랑 비슷하다고 한다.

슬라이딩 윈도우도 또 한 번 글을 써야 겠다.

 

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

 

---

 

#맞은 풀이

#include <bits/stdc++.h>

using namespace std;

int arr[3];
int dpmin[3];
int dpmax[3];


int main(){
    int n;
    cin >> n;
    //가장 처음 줄
    cin >>arr[0] >> arr[1] >> arr[2];
    
    //초기화
    for(int i = 0; i<3; i++){
        dpmax[i]=dpmin[i]=arr[i];
    }
    
    //이후 만들어갈 줄 (슬라이딩 윈도우)
    for(int i = 1; i<n; i++){
        int now0, now1, now2;
        cin >> now0 >> now1 >> now2;
        
        
        //dpmax값이 변하기 전값을 가지고 있어야함
        int tempMax_0 = dpmax[0];
        int tempMax_1 = dpmax[1];
        int tempMax_2 = dpmax[2];
        
        dpmax[0] = max(dpmax[0], dpmax[1]) + now0;
        dpmax[1] = max(max(tempMax_0, dpmax[1]),dpmax[2]) + now1;
        dpmax[2] = max(tempMax_1, dpmax[2]) + now2;
        
        int tempMin_0 = dpmin[0];
        int tempMin_1 = dpmin[1];
        int tempMin_2 = dpmin[2];
        
        dpmin[0] = min(dpmin[0], dpmin[1]) + now0;
        dpmin[1] = min(min(tempMin_0, dpmin[1]), dpmin[2]) + now1;
        dpmin[2] = min(tempMin_1, dpmin[2]) + now2;

    }
    
    cout << max(max(dpmax[0], dpmax[1]),dpmax[2]) << " ";
    cout << min(min(dpmin[0], dpmin[1]),dpmin[2]) << '\n';
    
}