백준 2096 내려가기 c++ // dp도안되면? 슬라이딩 윈도우

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

 

꽤나 애먹었던 문제이다...

1. 시간복잡도 분석

완탐 -> 3^100000 -> 시간초과

dp -> [y][x] -> 3*100000 -> 메모리초과(4MB) -> ??

 

2. 슬라이딩 윈도우

입력을 모두 받지않고, 입력이 들어오면 그때그때 처리한다.

모든입력에대해 아래 그림처럼 ㅁ 칸만 보고 그때그때 처리한다.

 

3. 의사코드

1. 역발상이 필요한데

mx배열중 가능한 최대값을 먼저 고른후, cur값과 더해야한다!

2. 주의사항

그 값을 pqr에 저장후 사용해야함

이유 : min[0] = min(mi[0], mi[1]) 이런식으로 진행되는데

위에서 min[0]값을 바꿔버리므로, 다음 min[1] 계산할때 오답이나온다.

 

 

#include <bits/stdc++.h>

using namespace std;

int n;
int pre1[3], pre2[3], cur1[3], cur2[3];
int mx[3], mi[3];


int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;

    for(int i=0 ;i<n ;++i) {
        int x, y, z;
        cin >> x >> y >> z;
        int p, q,r;
        p = max(mx[0], mx[1]);
        q = max({ mx[0], mx[1],mx[2] });
        r = max(mx[1], mx[2]);
        mx[0] = x + p;
        mx[1] = y + q;
        mx[2] = z + r;

        p = min(mi[0], mi[1]);
        q = min({ mi[0], mi[1], mi[2] });
        r = min(mi[1], mi[2]);
        mi[0] = x + p;
        mi[1] = y + q;
        mi[2] = z + r;

        /*cout << "[";
        for (int j = 0; j < 3; ++j) {
            cout << mi[j] << " ";
        }cout << "]\n";*/

    }
   

    cout << max({ mx[0],mx[1],mx[2] })<<" ";
    cout << min({ mi[0],mi[1],mi[2] }) << " ";

    return 0;

}