[BAE/<JOON> 문제풀이] 2096. 내려가기 (DP.044)

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

2096번: 내려가기

문제 티어가 골드 4라서 여러울거라 생각했는데 되게 간단했다.

 

문제의 핵심은 10만개의 입력이 주어지는데 반해 허용되는 메모리 한계가 4MB라는 점이다.

 

사실 이 부분도 unsigned short 로 변수를 선언하면  200,000 즉, 2MB로 떨어지므로 10만개 짜리 배열 2개를 써도

 

풀리지 않을까 생각했는데 그건 아니더라. (아마도 패딩때문에 그런 것 같다)

 

로직 자체는 간단하므로 배열만 빼면 쉽게 풀린다.

 

1. 입력을 저장하는 변수 3개

 

2. dp배열의 i-1번째 인덱스를 저장하는 변수 3개

 

2가지 변수를 선언하여 일번작인 해법을 그대로 적용하면 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    int x, y, z;
    int px = 0, py = 0, pz = 0;
    int spx = 0, spy = 0, spz = 0;
    cin >> n;
    int xx = 0, xy = 0, xz = 0;
    int nx = 0, ny = 0, nz = 0;
    for (int i = 1; i <= n; i++) {        
        cin >> x >> y >> z;
        xx = x + (px > py ? px : py);
        xy = y + max({ px, py, pz });
        xz = z + (py > pz ? py : pz);
        px = xx;
        py = xy;
        pz = xz;

        nx = x + (spx < spy ? spx : spy);
        ny = y + min({ spx, spy, spz });
        nz = z + (spy < spz ? spy : spz);
        spx = nx;
        spy = ny;
        spz = nz;
    }
    int mx = max({ px, py, pz });
    int mn = min({ spx, spy, spz });
    cout << mx << " " << mn;
    return 0;
}