제출 #377845

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
377845		dia312	배열 탈출 (GA8_array)	Cpython 3	49 / 100	1152 ms	65540 KiB

array

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

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