[17485] 진우의 달 여행 (Large)

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

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

dp[n][m][3] 형태로 테이블을 만들어서, 현재 방향과 다른 방향인 곳 2개중 작은것을 취한다.

편의상 1-base index를 사용하고, [1..n][1..m]이 아닌 다른곳은 INF로 채워주어서

방향을 신경쓰지 않고 min()으로 선택하는 도중에 자연스럽게 배제되도록 하였는데,

계산 과정중 a[i][j] + INF가 INT_MAX를 넘으면 문제가 될 수 있겠다.

이 문제에서 그리 큰 INF값은 필요없으니, 적당히 큰 값으로 잡아주자.

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

constexpr int INF = 1 << 29;

int n, m, a[1005][1005], dp[1005][1005][3];

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    cin >> n >> m;

    int i, j;

    for (i = 1; i <= n; i++)

        for (j = 1; j <= m; j++) cin >> a[i][j];

    for (i = 0; i <= n + 1; i++)

        for (j = 0; j <= m + 1; j++)

            dp[i][j][0] = dp[i][j][1] = dp[i][j][2] = INF;

    for (i = 0; i <= m + 1; i++)

        for (j = 0; j < 3; j++) dp[0][i][j] = 0;

    for (i = 1; i <= n; i++) {

        for (j = 1; j <= m; j++) {

            dp[i][j][0] =

                a[i][j] + min(dp[i - 1][j + 1][1], dp[i - 1][j + 1][2]);

            dp[i][j][1] = a[i][j] + min(dp[i - 1][j][0], dp[i - 1][j][2]);

            dp[i][j][2] =

                a[i][j] + min(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1]);

        }

    }

    int ans = INT_MAX;

    for (i = 1; i <= m; i++)

        for (j = 0; j < 3; j++) ans = min(dp[n][i][j], ans);

    cout << ans;

    return 0;

}

---