[백준] 2096 내려가기

백준: 문제

2096번: 내려가기

처음에는 단순한 DP 문제인줄 알았는데, 메모리를 줄이는 게 관건인 문제였다. 

N의 최대 크기는 100,000으로 배열 크기를 그만큼 잡아야한다고 생각했다. 하지만 잘 생각해보면 직전 줄의 값만 필요하고 그보다 이전 줄의 값은 필요하지 않다. 따라서 이전 줄과 현재 줄의 값만 저장하면 되므로 long long dp[2][3]만 있으면 된다.

경우의 수 

dp 배열의 크기를 줄여도 여전히 메모리를 줄이라는 경고 문자가 뜬다. 즉 주어진 입력값을 저장하는 배열조차도 줄이라는 뜻이었다. 그래서 바로 입력을 받아서 최댓값을 구하는 dp와 최솟값을 구하는 dp를 바로 풀어낸다. 이 때 코드의 수를 줄이기 위해 2번째 숫자는 모든 경우의 수에 다 쓰인다는 점을 조건부 삼항 연산자를 사용해서 작성하였다. 

최댓값, 최솟값 구하기

매번 O(logN)의 방식으로 최댓값을 구하였으나 sort 메소드를 사용하면 조금 더 간결하고 빠르게 최댓값과 최솟값을 찾아낼 수 있다.

 

0, 1로 순서 바꾸기

또한 이전 줄과 현재 줄을 번갈아 바꾸어가기 위해 변수 turn을 이용한다. turn = 1 - turn을 활용하면 원래 turn이 0일 때 1이 되고, 원래 1일 때 0이 된다. 

 

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
long long arr[3];
long long maxdp[2][3] = {0};
long long mindp[2][3] = {0};
int main(void){
    int n, turn = 1;
    cin >> n;
    for(int i = 0;i < n;i++){
        for(int j = 0;j < 3;j++){
            cin >> arr[j];
            maxdp[turn][j] = max(maxdp[1 - turn][1], (j == 1) ? max(maxdp[1 - turn][0], maxdp[1 - turn][2]) : maxdp[1 - turn][j]);
            mindp[turn][j] = min(mindp[1 - turn][1], (j == 1) ? min(mindp[1 - turn][0], mindp[1 - turn][2]) : mindp[1 - turn][j]);
            maxdp[turn][j] += arr[j];
            mindp[turn][j] += arr[j];
        }
        turn = 1 - turn;
    }
    sort(maxdp[1 - turn], maxdp[1 - turn] + 3);
    sort(mindp[1 - turn], mindp[1 - turn] + 3);
    cout << maxdp[1-turn][2] << " " << mindp[1-turn][0];
}