백준 2096번: 내려가기

백준 2096번: 내려가기

2096번: 내려가기

메모리가 4MB이므로 변수의 크기를 최소화 해야한다.

dp를 선언할 때 max와 min을 저장하는 것을 따로 설정하고

N만큼 반복하면서 max와 min일 때 모든 경우의 값을 저장하면은 해결이된다.

 

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    int score[3];
    int dp[2][3]; //0:max 1:min
    int tmp[2][3];
    int res1, res2;
    memset(tmp, 0, sizeof(tmp));
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            cin >> score[j];
        }
        tmp[0][0] = max(dp[0][0], dp[0][1]) + score[0];
        tmp[1][0] = min(dp[1][0], dp[1][1]) + score[0];
        tmp[0][1] = max(dp[0][0], max(dp[0][1], dp[0][2])) + score[1];
        tmp[1][1] = min(dp[1][0], min(dp[1][1], dp[1][2])) + score[1];
        tmp[0][2] = max(dp[0][1], dp[0][2]) + score[2];
        tmp[1][2] = min(dp[1][1], dp[1][2]) + score[2];
        for(int k = 0; k < 2; k++)
        {
            for(int l = 0; l < 3; l++)
            {
                dp[k][l] = tmp[k][l];
            }
        }
    }

    res1 = max(dp[0][0], max(dp[0][1], dp[0][2]));
    res2 = min(dp[1][0], min(dp[1][1], dp[1][2]));
    cout << res1 << " " << res2;
    return 0;
}