백준 2096번 내려가기

🔒[문제 url]

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

🔑알고리즘

dp[2][3][2]로 선언하여 메모리 초과를 방지한다.
dp[x][y][z]에서 각 index는 다음을 의미한다.

• x : 0이면 윗 줄, 1이면 현재 줄
• y : 행
• z : 0은 최대 점수, 1은 최소 점수
  
  
• 현재 줄에서, 각 행마다 유입 가능한 윗 줄을 순회하며
  현재 줄에서의 최대 점수, 최소 점수를 갱신한다.

🐾부분 코드

pair<int,int> setDP(int x, int y)
{

    int Max = -1; int Min = 2e9;

    for(int i = 0; i < 3; i++)
    {
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];

        if(0 <= ny && ny < 3)
        {
            Max = max(Max, dp[0][ny][0]);
            Min = min(Min, dp[0][ny][1]);
        }
    }

	// 유입 가능한 경로 중 최대.최소 점수에 현재 지점의 점수를 더한다.
    return {Max + map[x][y],Min + map[x][y]};
}

<DP 갱신 함수>
한 줄을 이동할 때마다, 유입 가능한 경로를 순회하며 최대 점수와 최소 점수를 갱신한다.

🪄전체 코드

#include <iostream>
#include <algorithm>
using namespace std;

int n;
int map[100'001][3];
int dp[2][3][2];
int dir[3][2] = {{-1,-1},{-1,0},{-1,1}};

void INPUT()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < 3; j++)
            cin >> map[i][j];
}

pair<int,int> setDP(int x, int y)
{

    int Max = -1; int Min = 2e9;

    for(int i = 0; i < 3; i++)
    {
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];

        if(0 <= ny && ny < 3)
        {
            Max = max(Max, dp[0][ny][0]);
            Min = min(Min, dp[0][ny][1]);
        }
    }

	// 유입 가능한 경로 중 최대.최소 점수에 현재 지점의 점수를 더한다.
    return {Max + map[x][y],Min + map[x][y]};
}


void SOLVE()
{
	// Initialize
    dp[1][0][0] = map[0][0]; dp[1][0][1] = map[0][0];
    dp[1][1][0] = map[0][1]; dp[1][1][1] = map[0][1];
    dp[1][2][0] = map[0][2]; dp[1][2][1] = map[0][2];

    for(int i = 1; i < n; i++)
    {
    	// Move row
        dp[0][0][0] = dp[1][0][0]; dp[0][0][1] = dp[1][0][1];
        dp[0][1][0] = dp[1][1][0]; dp[0][1][1] = dp[1][1][1];
        dp[0][2][0] = dp[1][2][0]; dp[0][2][1] = dp[1][2][1];

        for(int j = 0; j < 3; j++)
        {
            pair<int,int> DP = setDP(i,j);
            dp[1][j][0] = DP.first;
            dp[1][j][1] = DP.second;
        }
    }

    cout << max(max(dp[1][0][0],dp[1][1][0]),dp[1][2][0]) << " "
    << min(min(dp[1][0][1],dp[1][1][1]),dp[1][2][1]);

}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

문제는 뚝딱 풀었지만, 공간 복잡도 계산을 못해서 dp 배열 선언하면서도 되...되나..? 했던 문제이다.
고정 공간은 1.2MB정도 되는데, 가변 공간 메모리가 얼마나 나올지를 예측할 수가 없어서 조마조마했다.
결과는 3.2MB로 겨우(?) 통과한 것같은데.. 더 훌륭한 코드가 있나 찾아봐야겠다.