[백준] 2096 내려가기

문제 링크

http://icpc.me/2096

2096번: 내려가기

풀이

메모리를 줄여서 사용해야 하는 dp문제이다.

dp[i][j] = max(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) + arr[i][j]

dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) + arr[i][j]

위와 같은 점화식을 세울 수 있다.

점화식을 계산할 때 이전층까지의 정보만이 필요하기 때문에 전부 기억할 필요가 없다.

코드

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
int arr[N][5];
int dp[5][2];
int tmp[5][2];

int main() {
    int n; cin >> n;
    dp[0][1] = dp[4][1] = -1e8;
    dp[0][0] = dp[4][0] = 1e8;

    for (int i = 1; i <= n; i++) {
        cin >> arr[i][1] >> arr[i][2] >> arr[i][3];
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= 3; j++) {
            tmp[j][0] = min({dp[j - 1][0], dp[j][0], dp[j + 1][0]}) + arr[i][j];
            tmp[j][1] = max({dp[j - 1][1], dp[j][1], dp[j + 1][1]}) + arr[i][j];
        }
        for (int j = 1; j <= 3; j++) {
            dp[j][0] = tmp[j][0];
            dp[j][1] = tmp[j][1];
        }
    }
    
    printf("%d %d", max({dp[1][1], dp[2][1], dp[3][1]}), min({dp[1][0], dp[2][0], dp[3][0]}));
}