백준 온라인 저지, 다이나믹프로그래밍 / 11909번: 배열탈출 (파이썬 / , 백준 골드문제)

문제

상수는 2차원 배열 A[1..n][1..n] (n≥2, n은 자연수)을 가지고 있습니다. 이 배열의 각 원소는 1 이상 222 이하의 정수입니다.

배열을 가지고 놀던 상수를 본 승현이는, 질투심이 불타올라 상수를 A[1][1]에 가둬 버렸습니다! 최소한의 양심이 있던 승현이는 A[n][n]에 출구를 만들어 놓고 이 사실을 상수에게 알려줬습니다.

[그림 1] n=4라면 상수는 A[1,1]에 있고, 출구는 A[4][4]에 있습니다.

상수는 가능한 한 빨리 출구인 A[n][n]에 도달하고자 합니다. 상수가 A[i][j]에 있다고 가정했을 때, 상수는 최단 경로로 이동하기 위해 아래와 같은 조건을 만족하며 이동합니다.

1. 1≤i,j<n이라면, 상수는 A[i][j+1] 또는 A[i+1][j]로만 건너갑니다.
2. i=n,1≤j<n이라면, A[i][j+1]로만 건너갑니다.
3. 1≤i<n,j=n이라면 A[i+1][j]로만 건너갑니다.
4. i=j=n인 경우 바로 출구로 갑니다.

[그림 2] n=5라고 가정합시다. (ㄱ)는 1번 조건을 만족하고, (ㄴ)는 2번 조건을 만족하며, (ㄷ)는 3번 조건을 만족합니다.

그러나 건너갈 때에도 제약이 따릅니다. 상수가 A[a][b]에서 A[c][d]로 건너가려면 A[a][b]>A[c][d]를 만족해야 합니다. 상수는 왜인지 이런 조건을 만족하면서 이동할 수 없을 것 같았습니다. 다행히도, 승현이가 상수를 배열에 가둬버리기 전에, 상수는 배열의 각 원소에 버튼을 만들어 놓아서, 이 버튼을 누르면 해당 원소의 값이 1 증가하도록 했습니다. (물론 상수는 자신이 위치해 있는 원소의 버튼만 누를 수 있습니다.) 이 버튼 덕분에, 상수는 항상 배열을 탈출할 수 있습니다!

[그림 3] n=2라고 가정합시다. A[1][1]=5>A[1][2]=2이므로, 상수는 A[1][1]에서 A[1][2]로 건너갈 수 있습니다. 상수가 A[1][1]에서 A[2][1]로 건너가려면, A[1][1]에 있는 버튼을 두 번 눌러 A[1][1]의 값을 7로 만들면 됩니다.

하지만 버튼을 한 번 누르는 데에는 1원의 비용이 듭니다. 상수는 돈을 가능한 한 적게 들이면서 배열을 탈출하고자 합니다. 상수를 도와주세요.

입력

첫 번째 줄에 n이 주어집니다. (n ≤ 2,222)

다음에 n개 줄이 주어집니다. 이 중 i(1≤i≤n)번째 줄에는 n개의 수 A[i][1],A[i][2],⋯,A[i][n−1],A[i][n]이 공백을 사이로 두고 차례대로 주어집니다.

출력

첫 번째 줄에 상수가 배열을 탈출하기 위해 들여야 할 최소 비용(원 단위)을 출력합니다.

 

제한

예제 입력 1

4
5 2 4 3
6 5 1 2
3 4 5 3
7 4 3 1

예제 출력 1

3

예제 입력 2

5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

예제 출력 2

8

힌트

상수는 아래 그림과 같은 방법으로 탈출할 수 있습니다.

이렇게 하면 A[1][1]에서 2원, A[3][2]에서 1원의 비용이 들어 총 3원의 비용이 들게 되며, 이것이 최소입니다.

접근 방법

- 작은 숫자의 행부터 하나씩 탐색해나가며 (현재 행 - 1, 현재 열)까지 움직이는 데 든 돈과 해당 위치에서 현재 위치까지 움직이는 데 든 돈을 합한 것과 (현재 행, 현재 열 - 1)까지 움직이는 데 든 돈과 현재 위치까지 움직이는데 든 돈을 합한 것을 비교해 작은 값으로 갱신한다.
- 가장 마지막 열에 도달했을 때 거기까지 이동하기 위해 든 비용을 계산해 출력한다.

코드

# https://www.acmicpc.net/problem/11909
# 접근 방법
# 작은 숫자의 행부터 하나씩 탐색해나가며 (현재 행 - 1, 현재 열)까지 움직이는 데 든 돈과 해당 위치에서 현재 위치까지 움직이는 데 든 돈을 합한 것과 (현재 행, 현재 열 - 1)까지 움직이는 데 든 돈과 현재 위치까지 움직이는데 든 돈을 합한 것을 비교해 작은 값으로 갱신한다.
# 가장 마지막 열에 도달했을 때 거기까지 이동하기 위해 든 비용을 계산해 출력한다.
import sys
input = sys.stdin.readline
n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
dp = [[0 for _ in range(n)] for _ in range(n)]
for r in range(n):
    for c in range(n):
        if 0>r-1 and 0>c-1:
            continue
        prev_r, prev_c = int(1e7), int(1e7)
        if 0<=r-1:
            prev_r = dp[r-1][c] + (0 if arr[r][c] < arr[r-1][c] else arr[r][c] - arr[r-1][c] + 1)
        if 0<=c-1:
            prev_c = dp[r][c-1] + (0 if arr[r][c] < arr[r][c-1] else arr[r][c] - arr[r][c-1] + 1)
        dp[r][c] = min(prev_r, prev_c)
print(dp[n-1][n-1])