내려가기 - 2096

//2096 - 내려가기
 
#include <iostream>
using namespace std;
 
#define INF 100000000
 
int N;
int arr[100000][3];
int cache[2][3];
int cache2[2][3];
 
void init()
{
    cin >> N;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < 3; ++j)
            cin >> arr[i][j];
}
 
int dp(int x, int y)
{
    if (y == -1 || y == 3)
        return -1;
    if (x == N - 1)
        return arr[x][y];
 
    return cache[x % 2][y];
}
 
int dp2(int x, int y)
{
    if (y == -1 || y == 3)
        return INF;
    if (x == N - 1)
        return arr[x][y];
 
    return cache2[x % 2][y];
}
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    init();
    for(int i = 0; i<3; ++i)
        cache[0][i] = cache2[0][i] = arr[0][i];
    for (int i = N - 2; i >= 0; --i)
    {
        for (int j = 0; j < 3; ++j)
            cache[i % 2][j] = -1, cache2[i % 2][j] = INF;
 
        for (int j = 0; j < 3; ++j)
        {
            for (int k = -1; k <= 1; ++k)
                cache[i % 2][j] = max(cache[i % 2][j], dp(i + 1, j + k)),
                cache2[i % 2][j] = min(cache2[i % 2][j], dp2(i + 1, j + k));
            cache[i % 2][j] += arr[i][j];
            cache2[i % 2][j] += arr[i][j];
        }
    }
    int ans = 0, ans2 = INF;
    for (int i = 0; i < 3; ++i)
        ans = max(ans, cache[0][i]), ans2 = min(ans2, cache2[0][i]);
    cout << ans << " " << ans2;
}

 

 

 

 

 

 

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

2096번: 내려가기

 

 

 

 

 

 

내려가기

Cmin(x, y) : (x, y)까지 진행한 것중 가장 작은 값

Cmax(x, y) : (x, y)까지 진행한 것중 가장 큰 값

Cmin(x, y) = (-1 <= k <= 1)min{Cmin(x+1, y+k)} + arr[x][y]

Cmax(x, y) = (-1 <= k <= 1)max{Cmax(x+1, y+k)} + arr[x][y]

 

처음에는 위의 점화식으로 재귀함수를 만들어 해결하려 했습니다. 하지만 기본적으로 소모되는 메모리에 cache를 위한 4*100000*3 만큼의 바이트로인해 메모리 초과가 발생하였습니다.

더 좋은 점화식을 생각해 내지 못했고, 또 제가 알고있는 점화식에선 현재 단계를 생성하기 위해 오직 이전단계만을 필요로 하기에, 반복문을 이용한 dp에 슬라이딩 윈도 기법을 이용하여 메모리 사용량을 줄여주었습니다.

(재귀함수 dp는 슬라이딩윈도 기법을 사용할 수 없습니다.)