[BOJ] 2096 내려가기

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

2096번: 내려가기

사용가능한 메모리가 4MB라는 것을 주의해야 한다.

나는 평소 dp처럼 모든 값을 받고 연산하는 것이 아니라 메모리를 줄이기 위해 값을 받을 때마다 연산하도록 구현하였다.

max_배열과 min_배열을 이용하였는데 max_에는 현재까지 내려가는 비용의 최댓값을, min_배열에는 현재까지 내려가는 비용의 최솟값을 저장해 주었다. 

#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>

#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

int max_[2][3];
int min_[2][3];
int arr[3];
int N,ans1,ans2;

void input() {
    cin>>N;
}

void init() {
    for(int i=0;i<3;i++) cin>>arr[i];
    for(int i=0;i<3;i++){
        max_[0][i]=arr[i];
        min_[0][i]=arr[i];
    }
}

void solution() {
    for(int i=1;i<N;i++){
        for(int j=0;j<3;j++) cin>>arr[j];
        
        //left
        max_[1][0]=arr[0]+max(max_[0][0],max_[0][1]);
        min_[1][0]=arr[0]+min(min_[0][0],min_[0][1]);
        
        //middle
        max_[1][1]=arr[1]+max(max_[0][2],max(max_[0][0],max_[0][1]));
        min_[1][1]=arr[1]+min(min_[0][2],min(min_[0][0],min_[0][1]));
        
        //right
        max_[1][2]=arr[2]+max(max_[0][1],max_[0][2]);
        min_[1][2]=arr[2]+min(min_[0][1],min_[0][2]);
        
        for(int j=0;j<3;j++) max_[0][j]=max_[1][j];
        for(int j=0;j<3;j++) min_[0][j]=min_[1][j];
    }
    
    ans1=max(max_[0][2],max(max_[0][0],max_[0][1]));
    ans2=min(min_[0][2],min(min_[0][0],min_[0][1]));
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    init();
    solution();
    cout<<ans1<<' '<<ans2;
    return 0;
}