This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
import sys, heapq
input=sys.stdin.readline
INF = int(1e9)
n = int(input())
maps = []
maps.append([INF]*(n+1))
#배열 입력
for i in range(n):
tmp = [INF]+list(map(int,input().split()))
maps.append(tmp)
#비용 초기화
cost = [[0]*(n+1) for _ in range(n+1)]
cost[1][1]=0
#디피
for i in range(1,n+1):
for j in range(1,n+1):
if j-1==0 and i-1==0:
continue
elif j-1==0:
button2 = cost[i-1][j] if maps[i][j]<maps[i-1][j] else maps[i][j]-maps[i-1][j] + 1 + cost[i-1][j]
cost[i][j]+=button2
elif i-1==0:
button1 = cost[i][j-1] if maps[i][j]<maps[i][j-1] else maps[i][j]-maps[i][j-1] + 1 + cost[i][j-1]
cost[i][j]+=button1
else:
button1 = cost[i][j-1] if maps[i][j]<maps[i][j-1] else maps[i][j]-maps[i][j-1] + 1 + cost[i][j-1]
button2 = cost[i-1][j] if maps[i][j]<maps[i-1][j] else maps[i][j]-maps[i-1][j] + 1 + cost[i-1][j]
cost[i][j]+=min(button1,button2)
print(cost[n][n])
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |