[Algorithm]Baekjoon 17485번 :: 진우의 달 여행 (Large)

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

17485번: 진우의 달 여행 (Large)

 
int arr[1001][1001] = { 0 };
int dp[1001][1001][3] = { 0 };
int n, m;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m;
 
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            cin >> arr[i][j];
        }
    }
 
    memset(dp, 0x3f, sizeof(dp));
 
    for (int i = 0; i <= m; ++i)
    {
        dp[0][i][0] = dp[0][i][1] = dp[0][i][2] = 0;
    }
    int answer = 0x3f3f3f3f;
 
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            if (j == 1) // 맨 왼쪽
            {
                dp[i][j][1] = dp[i - 1][j + 1][0] + arr[i][j];
                dp[i][j][2] = min(dp[i - 1][j][1],dp[i-1][j+1][0]) + arr[i][j];
            }
            else if (j == m) // 맨 오른쪽
            {
                dp[i][j][1] = dp[i - 1][j - 1][2] + arr[i][j];
                dp[i][j][0] = min(dp[i - 1][j][1], dp[i - 1][j - 1][2]) + arr[i][j];
            }
            else // 그 외
            {
                dp[i][j][0] = min(dp[i - 1][j - 1][2], dp[i - 1][j][1]) + arr[i][j];
                dp[i][j][1] = min(dp[i - 1][j - 1][2], dp[i - 1][j + 1][0]) + arr[i][j];
                dp[i][j][2] = min(dp[i - 1][j][1], dp[i - 1][j + 1][0]) + arr[i][j];
            }
 
            if (i == n)
            {
                answer = min(answer, min(min(dp[i][j][0], dp[i][j][1]), dp[i][j][2]));
            }
        }
    }
 
    cout << answer;
}
 
 
 

 

목적지까지 최소의비용으로 도달해야하는 연습문제로 적절한 DP문제이다.

이 문제에서의 포인트는, 이전에 진행했던 방향으로는 다시 진행할 수 없다는 것이다. 

이 점을 표현하기위해 3차원 DP테이블로 표현했다.

 

예를들어 dp[i][j][0] 은, [i][j]위치에서 왼쪽대각선으로 이동하려할 때의 연료최솟값이다. (1은 직진, 2는 오른쪽대각선)

그렇기 때문에 dp[i][j][0]값을 업데이트하기 위해서는 이전행에서 이 위치에 도달할 때 왼쪽대각선으로 이동했으면 안되고, 중앙방향,오른쪽 대각선으로 i,j 위치에 도달했어야 한다.

중앙방향으로 i,j에 도달하려면 i-1,j에서 움직여야하고  오른쪽 대각선으로 i,j위치에 도달하려면 i-1,j-1에서 움직여야한다.

그렇기 때문에   dp[i][j][0] = min(dp[i - 1][j - 1][2], dp[i - 1][j][1]) + arr[i][j];

 

이 성립하게 된다.