[C/C++] 백준 #2096 내려가기(동적 계획법)

내려가기 문제는 간단한 형태의 동적 계획법(Dynamic Programming)을 사용하면 됩니다.

동적 계획법을 사용하지 않고, DFS나 BFS를 이용해서 풀 수는 있지만, 그렇게 하면 시간이 많이 걸립니다.  다익스트라 알고리즘을 사용해도 동적 계획법을 적용한 것과 같은 효과를 낼 수 있습니다.

 

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

2096번: 내려가기

 

처음에는 설명을 이해하기 어려웠습니다.

 

주어진 N이 주어지면, 3xN 형태의 공간이 발생합니다.  맨 위층에서는 3칸 중 아무곳이나 선택할 수 있습니다.  그 다음부터는 바로 아래칸 또는 아래칸의 왼쪽칸, 또는 오른쪽 칸으로 이동할 수 있습니다.  총 N칸을 다 들리게 되면 아래에 도달하게 됩니다.

예를 들어서 N=3이고, 각 칸의 값이 주어진다면,

1	2	3
4	5	6
4	9	0

형태가 됩니다.

맨 윗칸에서 1을 선택했다면, 갈 수 있는 칸을 바로 아래칸인 4와 그 오른쪽 칸인 5로 갈 수 있습니다.  

그때 경로에 있는 값들의 합의 최소와 최대값을 선택하면 됩니다.

 

1	2	3
4	5	6
4	9	0

 

위와 같이 이동하면, 총 합이 6이 되어서 최소값을 가집니다.

 

1	2	3
4	5	6
4	9	0

이렇게 이동을 하면 합이 18이 되어서 최대값을 가집니다.

 

동적계획법을 이용하게 되면, 가운데 줄에서는 3군데에서 오는 값들의 최대값을 저장하면 되고, 첫번째 줄과 마지막 줄은 2군데에서 오는 값들 중 최대값을 저장하면 됩니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2096 - Step down
//        - by Aubrey Choi
//        - created at 2019-06-14
//------------------------------------------------
#include <stdio.h>

int MAX(int a,int b,int c) { int max=a; if(b>max) max=b; if(c>max) max=c; return max; }
int MAX(int a,int b) { return a > b ? a : b; }
int MIN(int a,int b,int c) { int min=a; if(b<min) min=b; if(c<min) min=c; return min; }
int MIN(int a,int b) { return a < b ? a : b; }
int main()
{
    int n, max, min, i;
    static int dp[100000][3], value[100000][3];
    scanf("%d", &n);
    for(i = 0; i < n; i++) scanf("%d%d%d",&value[i][0],&value[i][1],&value[i][2]);
    dp[0][0] = value[0][0];
    dp[0][1] = value[0][1];
    dp[0][2] = value[0][2];
    for(i = 1; i < n; i++)
    {
        dp[i][0] = MAX(dp[i - 1][0], dp[i-1][1]) + value[i][0];
        dp[i][1] = MAX(dp[i - 1][0], dp[i-1][1], dp[i-1][2]) + value[i][1];
        dp[i][2] = MAX(dp[i - 1][1], dp[i-1][2]) + value[i][2];
    }
    max = MAX(dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]);
    for(i = 1; i < n; i++)
    {
        dp[i][0] = MIN(dp[i - 1][0], dp[i - 1][1]) + value[i][0];
        dp[i][1] = MIN(dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]) + value[i][1];
        dp[i][2] = MIN(dp[i - 1][1], dp[i - 1][2]) + value[i][2];
    }
    min = MIN(dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]);
    printf("%d %d\n", max, min);
}