Submission #378140

#	Time	Username	Problem	Language	Result	Execution time	Memory
378140		dia312	배열 탈출 (GA8_array)	Pypy 2	49 / 100	431 ms	65540 KiB

array

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()

• Subtask 1: 6 / 6
• Subtask 2: 11 / 11
• Subtask 3: 32 / 32
• Subtask 4: 0 / 51