[백준][2096번][DP] 내려가기

내려가기

 

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

 

<문제>

 

<코드>

 

#include  <stdio.h>
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
 
int tower[3];
int DpMax[100001][3];
int DpMin[100001][3];
 
int main(void)
{
    int n;
    scanf("%d",&n);
     
    for(int i=1;i<=n;i++)
    {
        scanf("%d %d %d", &tower[0], &tower[1], &tower[2]);
            
           DpMax[i][0] = Max(DpMax[i-1][0] , DpMax[i-1][1]) + tower[0]; 
           DpMax[i][1] = Max(Max(DpMax[i-1][0] , DpMax[i-1][1]),DpMax[i-1][2]) + tower[1]; 
           DpMax[i][2] = Max(DpMax[i-1][1] , DpMax[i-1][2]) + tower[2]; 
     
           DpMin[i][0] = Min(DpMin[i-1][0] , DpMin[i-1][1]) + tower[0]; 
           DpMin[i][1] = Min(Min(DpMin[i-1][0] , DpMin[i-1][1]),DpMin[i-1][2]) + tower[1]; 
           DpMin[i][2] = Min(DpMin[i-1][1] , DpMin[i-1][2]) + tower[2]; 
     
    }
     
   
     
    printf("%d %d\n", Max(Max(DpMax[n][0],DpMax[n][1]),DpMax[n][2]) ,  Min(Min(DpMin[n][0] , DpMin[n][1]),DpMin[n][2]));
    
     
    return 0;
}
 

 

<문제 푼 요령>

 1. 여기서 중요한건 최대값을 구하는 경우와 최소값을 구하는 경우가 있기 때문에 DP 테이블을 두개로 나누어야 한다.

 2. DP 테이블은 DP[N][3] 꼴로 표현할 수 있는데 이 DP[N][0] , DP[N][1], DP[N][2] 의 값을 나누어서 생각하면 편하다. 즉 이 값들은 이전의 값과 연계되어서 값을 가질 수 있는데

DP[N][0] -> DP[N-1][0] 과 DP[N-1][1]

DP[N][1] -> DP[N-1][0] 과 DP[N-1][1] 과 DP[N-1][2] 

DP[N][2] -> DP[N-1][1] 과 DP[N-1][2]

 위에 같이 연관이 있는걸 알 수 있다 즉 DP 테이블의 이전의 값과 현재의 tower값을 더해서 우리가 원하는 최대값 혹은 최소값을 구할 수 있게 되는 것이다.