내려가기 2096번 [백준]

이번에 풀은 문제는 dp와 Sliding Window를 이용하여 풀는 문제였습니다.

 

문제는 1칸씩 내려가면서, bottom-top 내려오는 방식으로, 위의 dp값을 이용하여 아래의 dp값을 구하는 방식으로 풀었습니다.

메모리제한이 4메가 밖에 안되어, 입력은 반복을 할때마다 받았습니다.

#import<bits/stdc++.h>

using namespace std;
#define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

int main() {
    fast_io;
    int n;
    cin>>n;
    int arr[3];
    int dp_max[3];
    int dp_min[3];
    for(int i =0;i<3;i++){
        cin>>arr[i];
        dp_max[i] = dp_min[i] = arr[i];
    }
    int i =n-1;
    while(i--){
        cin>>arr[0]>>arr[1]>>arr[2];
        dp_max[0] = max(dp_max[1],dp_max[0]);
        dp_max[2] = max(dp_max[1],dp_max[2]);
        dp_max[1] = max(dp_max[0],dp_max[2])+arr[1];
        dp_max[0] += arr[0];
        dp_max[2] += arr[2];

        dp_min[0] = min(dp_min[1],dp_min[0]);
        dp_min[2] = min(dp_min[1],dp_min[2]);
        dp_min[1] = min(dp_min[0],dp_min[2])+arr[1];
        dp_min[0] += arr[0];
        dp_min[2] += arr[2];
    }
    cout<<*max_element(dp_max,dp_max+3)<<" "<<*min_element(dp_min,dp_min+3);
}

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