[백준 17485] 진우의 달 여행 (DP) (C/C++) (★)

#include <iostream>
#include <string>
#include <algorithm>
#include <string.h>
using namespace std;
 
int cost[1010][1010];
int dp[1010][1010][4]; // 0 : 왼쪽, 1 : 중앙, 2 : 오른쪽 
int row, col;
 
int solve(int x, int y, int dir)
{
    if(x == row)
    {
        return 0;
    }
    
    if(dp[x][y][dir] != 99999999)
    {
        return dp[x][y][dir];
    }
    
    // 왼쪽
    if(dir != 0 && y-1 >= 0)
    {
        dp[x][y][dir] = solve(x+1, y-1, 0) + cost[x][y];     
    } 
    
    // 중앙 
    if(dir != 1)
    {
        dp[x][y][dir] = min(dp[x][y][dir], solve(x+1, y, 1) + cost[x][y]);    
    }
    
    // 오른쪽
    if(dir != 2 && y+1 < col)
    {
        dp[x][y][dir] = min(dp[x][y][dir], solve(x+1, y+1, 2) + cost[x][y]); 
    } 
    
    return dp[x][y][dir];
}
 
int main(void)
{
//    freopen("B17485_input.txt", "r", stdin);
    
    cin >> row >> col;
    
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            cin >> cost[i][j];
            
            for(int k = 0; k < 4; k++)
            {
                dp[i][j][k] = 99999999;    
            }
        }
    }
     
    int Min = 99999999;
    for(int i = 0; i < col; i++)
    {
        // 처음에는 방향이 없기 때문에 dir에 3을 대입 
        Min = min(Min, solve(0, i, 3));
    }
    
    cout << Min;
    
    return 0;
}