[백준 c++] 2096 내려가기

---

문제

https://www.acmicpc.net/problem/2096
N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다.
첫 줄에서 시작해서 마지막 줄까지 내려가려고 한다.
내려갈 때는 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다.

---

풀이

bottom-up DP로 풀었다.
최댓값을 저장하는 dp_max , 최솟값을 저장하는 dp_min

단, N이 최대 100000이고 메모리 제한은 4 MB라서
모든 줄을 저장하지 않고 이전과 현재 줄만 저장하도록 한다.

---

코드

#include <iostream>
#include <algorithm>
using namespace std;
int n, a[100001][3], dp_max[2][3], dp_min[2][3];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < 3; j++)
            cin >> a[i][j];

    for (int i = 1; i <= n; i++)
    {
        dp_max[1][0] = max(dp_max[0][0], dp_max[0][1]) + a[i][0];
        dp_max[1][1] = max(max(dp_max[0][0], dp_max[0][1]), dp_max[0][2]) + a[i][1];
        dp_max[1][2] = max(dp_max[0][1], dp_max[0][2]) + a[i][2];

        dp_min[1][0] = min(dp_min[0][0], dp_min[0][1]) + a[i][0];
        dp_min[1][1] = min(min(dp_min[0][0], dp_min[0][1]), dp_min[0][2]) + a[i][1];
        dp_min[1][2] = min(dp_min[0][1], dp_min[0][2]) + a[i][2];

        for (int j = 0; j < 3; j++)
        {
            dp_max[0][j] = dp_max[1][j];
            dp_min[0][j] = dp_min[1][j];
        }
    }
    cout << max(max(dp_max[1][0], dp_max[1][1]), dp_max[1][2]) << " ";
    cout << min(min(dp_min[1][0], dp_min[1][1]), dp_min[1][2]) << "\n";
}