이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
import sys
input=sys.stdin.readline
INF = int(1e9)
n = int(input())
maps = [[INF]*(n+1)]
#배열 입력
for i in range(n):
maps.append([INF]+list(map(int,input().split())))
#비용 초기화
cost = [[0 for _ in range(n+1)] for _ in range(n+1)]
def cal(a,b):
if a>b:
return 0
else:
return b-a+1
#디피
def dp():
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:
cost[i][j]+=cal(maps[i-1][j],maps[i][j]) + cost[i-1][j]
elif i-1==0:
cost[i][j]+=cal(maps[i][j-1],maps[i][j]) + cost[i][j-1]
else:
cost[i][j]+=min(cal(maps[i][j-1],maps[i][j]) + cost[i][j-1],cal(maps[i-1][j],maps[i][j]) + cost[i-1][j])
print(cost[n][n])
dp()
# | 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... |