Informatica Online Judge

  배열 탈출 [2027 / 07EB]

Time Limit(Test case) : 3000 (ms)
Number of users who solved : 21   Total Tried : 24


The Champion of this Problem (C++) : gs15009 - 56ms / 829byte
My Best Submission (C++) : N/A

[GENIUSainta.com 제8회 모의고사]

Background

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

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



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


  • i!=n 이라면 상수는 A[i+1][j]로 건너갈 수 있습니다.

  • j!=n 이라면 상수는 A[i][j+1]로 건너갈 수 있습니다.

  • i=j=n인 경우 바로 출구로 갑니다.



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

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

Input

첫 번째 줄에 n이 주어집니다.

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

[주의] 입력이 아주 많으므로 C++에서 cin과 같은 입력을 사용하지 않는 것을 권장합니다. scanf를 사용해서 입력을 받아주세요.

[Sub-Task Info]
#1 : n=2
#2 : 2n≤22 (n≤11)
#3 : n≤222
#4 : n≤2,222

Output

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

IO Example

입력1
4
5 2 4 3
6 5 1 2
3 4 5 3
7 4 3 1

출력1
3

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



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

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]