백준 11909번: 배열 탈출 (C++)

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

11909번: 배열 탈출

---

Level: Gold V

Solved By: DP

 

처음에는 Dijkstra로 풀려고 했었습니다. pair<pair<int, int>, int> 같은 복잡한 자료형을 만들어서 구현했는데 메모리 초과로 다른 키워드를 생각해내야 했습니다. DP 태그가 달려있어서 DP로도 구현할 수 있겠다 싶었습니다.

 

제가 생각한 아이디어와 관계식은 아래와 같습니다

\(cache\)는 해당 원소로 갔을 때, 최단 경로 값을 저장할 2차원 배열이며, \(q\)는 원소 위치 별로 상수 값을 저장해 놓은 2차원 배열입니다.

$$ \begin{align}
cache(i, j) = min(cost_{1} + cache(i-1, j),\ cost_{2}+cache(i, j-1))\\ \\

cost_{1} = \left\{
\begin{array}{lr}
0 & : q(i, j) - q(i-1, j) <0\\
q(i,j) - q(i-1, j)+1 & : q(i, j) - q(i-1, j) \geq0
\end{array}
\right.\\ \\

cost_{2} = \left\{
\begin{array}{lr}
0 & : q(i, j) - q(i, j-1) <0\\
q(i,j) - q(i, j-1)+1 & : q(i, j) - q(i, j-1) \geq0
\end{array}
\right.

\end{align} $$

 

다만, 이러한 관계식이 적용되기 위해서는 당연히 고려되는 이전 원소들이 전부 다 업데이트가 되어있어야 합니다. (Bottom-Up)

그래서 이를 해결하기 위해 \(k=i+j\ (1 \leq k \leq 2 * N,\ 1\leq i \leq k)\)이와 같은 식을 만들어서 (1, 3), (2, 2), (3, 1) -> (1, 4), (2, 3)... 이런 순서대로 DP를 할 수 있도록 코드를 만들어줬습니다.

#include <iostream>
#define MAX 2223
#define INF 1e9
using namespace std;

int N;

int q[MAX][MAX];
int cache[MAX][MAX];

int main(){
    cin >> N;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j<= N; j++){
            cin >> q[i][j];
        }
    }
    
    for(int k = 3; k <= N + N; k++){
        for(int i = 1; i <= k; i++){
            int j = k - i;
            if(i > N || j > N) continue;
            
            int up = INF, left = INF;
            if(j - 1 > 0){
                int cost = (q[i][j-1] - q[i][j] > 0 ? 0 :q[i][j] - q[i][j-1] + 1);
                left = min(left, cost + cache[i][j-1]);
            }
            if(i - 1 > 0){
                int cost = (q[i-1][j] - q[i][j] > 0 ? 0 :q[i][j] - q[i-1][j] + 1);
                up = min(up, cost + cache[i-1][j]);
            }
            cache[i][j] = min(up, left);
        }
    }
    cout << cache[N][N];
    return 0;
}