백준 17856, Just Passing Through

개요

문제 링크
골드 4, DP
왼쪽 오른쪽보다 크고, 위아래보다 작은 지점을 n번 지나면서 가로로 이동하는 비용의 최솟값

---

접근

1. 문제풀이보다 번역이 더 까다로운 문제. 2차원 경로탐색 dp인데 n번 지난다 라는 변수가 있으므로 3차원 dp를 이용해야 한다. 2차원 경로탐색 -> 골5, 3차원 -> 랭크+1 로 골4로 책정한듯.
2. 우선 비용부터 생각하자. 비용은 왼위, 왼, 왼아래중 최솟값을 더하면 된다. 어떤 지점에 도달하기 위해서는 저렇게 세 가지 이전 점을 가지기 때문이다.
3. 그리고 pass조건이 조금 까다로운데, 만약 어떤 (x,y)가 pass에 속한다면 이전점에서 n-1개의 pass를 지나온 비용과 비교해 업데이트 한다. 그렇지 않다면 n개의 pass를 지나온 비용과 업데이트한다. 왜냐하면 그 점을 지나면서 pass가 하나 추가되기 때문이다.
4. pass를 정하는 조건은 continue를 쓰면 보다 깔끔하게 만들 수 있다.
   주의할 점은 보통 경로탐색이 위에서 아래로 이동하기 때문에 세로->가로 로 이중 포문을 돌리면 되지만 이 문제는 왼쪽에서 오른쪽으로 이동하기 때문에 가로->세로 로 이중 포문을 돌려야 한다는 것.

---

Pseudo code

for (x = 가로)
    for (y = 세로)
        if (left == -1) continue
        if (right == -1) continue
        if (up == -1) continue
        if (down == -1) continue
        if (left >= cur) continue
        if (right >= cur) continue
        if (up <= cur) continue
        if (down <= cur) continue
        pass[y][x] = true

for (x = 가로)
    for (y = 세로)
        if (cur == -1) continue
        for (n = 1~n)
            is_pass = pass[y][x]
            left_up = dp[y-1][x-1][n-is_pass]
            left = dp[y][x-1][n-is_pass]
            left_down = dp[y+1][x][n-is_pass]
            dp[y][x][n] = min(left_up,left,left_down)+cur

---

Source code

#include <iostream>
using namespace std;

int main() {
    int r, c, n;
    cin >>r>>c>>n;
    int a[r+2][c+2],p[r+2][c+2];
    for (int i=0; i<=r+1; i++)
        for (int j=0; j<=c+1; j++)
            a[i][j]=-1, p[i][j]=0;
    for (int i=1; i<=r; i++)
        for (int j=1; j<=c; j++)
            cin >> a[i][j];

    int dp[r+2][c+2][n+1];
    for (int i=1; i<=r; i++)
        for (int j=1; j<=c; j++) {
            if (a[i-1][j]==-1) continue;
            if (a[i][j-1]==-1) continue;
            if (a[i+1][j]==-1) continue;
            if (a[i][j+1]==-1) continue;

            int v = a[i][j];
            if (a[i-1][j]<=v) continue;
            if (a[i+1][j]<=v) continue;
            if (a[i][j-1]>=v) continue;
            if (a[i][j+1]>=v) continue;
            p[i][j] = 1;
        }
    for (int i=0; i<=r+1; i++)
        for (int j=0; j<=c+1; j++)
            for (int k=0; k<=n; k++)
                dp[i][j][k] = 2e9;

    for (int j=1; j<=c; j++)
        for (int i=1; i<=r; i++) {
            if (a[i][j]==-1) continue;
            for (int k=0; k<=n; k++) {
                int d = p[i][j];
                if (k==0&&d) continue;
                int v = 2e9;
                v = min(v,dp[i-1][j-1][k-d]);
                v = min(v,dp[i+1][j-1][k-d]);
                v = min(v,dp[i][j-1][k-d]);
                if (k==0&&j==1) v=0;
                dp[i][j][k] = v+a[i][j];
            }
        }
    int ans = 2e9;
    for (int i=1; i<=r; i++)
        ans = min(ans,dp[i][c][n]);
    if (ans==2e9) cout << "impossible";
    else cout << ans;
}