82)알리바바와 40인의 도둑(Bottom-Up)

문제

N*N의 계곡의 돌다리 격자정보가 주어지면 (1, 1)격자에서 (N, N)까지 가는데 드는 에너지의 최소량을 구하는 프로그램을 작성하기

 

조건

계곡의 돌다리는 N×N개의 돌들로 구성되어 있다.

 

각 돌다리들은 높이가 서로 다릅니다.

 

해당 돌다리를 건널때 돌의 높이 만큼 에너지가 소비됩니다.

 

이동은 최단거리 이동을 합니다. 즉 현재 지점에서 오른쪽 또는 아래쪽으로만 이동해야 합니다.

 

만약 N=3이고, 계곡의 돌다리 격자 정보가 다음과 같다면

 

(1, 1)좌표에서 (3, 3)좌표까지 가는데 드는 최소 에너지는 3+2+3+4+2=14이다.

 

제한사항

첫 번째 줄에는 자연수 N(1<=N<=20)이 주어진다.

 

두 번째 줄부터 계곡의 N*N 격자의 돌다리 높이(10보다 작은 자연수) 정보가 주어진다.

 

첫 번째 줄에 (1, 1)출발지에서 (N, N)도착지로 가기 위한 최소 에너지를 출력한다.

 

문제풀이

N=int(input())
a=[list(map(int, input().split())) for _ in range(N)]
dy=[[0]*N for _ in range(N)]
dy[0][0]=a[0][0]

for i in range(N):
  dy[0][i]=dy[0][i-1]+a[0][i]
  dy[i][0]=dy[i-1][0]+a[i][0]

for i in range(1, N):
  for j in range(1, N):
    dy[i][j]=min(dy[i-1][j], dy[i][j-1])+a[i][j]

print(dy[N-1][N-1])