[Python Algorithm] Dynamic programming(동적계획법) - 알리바바와 40인의 도둑(Bottom-Up)

> Dynamic programming(동적계획법)

 

 

 

 

 

📖 문제 : 알리바바와 40인의 도둑(Bottom-Up)

 

알리바바는 40인의 도둑으로부터 금화를 훔쳐 도망치고 있습니다.

알리바바는 도망치는 길에 평소에 잘 가지 않던 계곡의 돌다리로 도망가고자 한다. 계곡의 돌다리는 N×N개의 돌들로 구성되어 있다. 각 돌다리들은 높이가 서로 다릅니다.

해당 돌다리를 건널때 돌의 높이 만큼 에너지가 소비됩니다. 이동은 최단거리 이동을 합니다. 즉 현재 지점에서 오른쪽 또는 아래쪽으로만 이동해야 합니다. N*N의 계곡의 돌다리 격자정보가 주어지면 (1, 1)격자에서 (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)도착지로 가기 위한 최소 에너지를 출력한다.

 

 

입력예제 1

5
3 7 2 1 9

5 8 3 9 2

5 3 1 2 3

5 4 3 2 1

1 7 5 2 4

 

 

출력예제 1

25

 

 

 

내 코드

if __name__ == "__main__":

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

    summ = arr[0][0]
    dy[0][0] = arr[0][0]


    for i in range(n):
        
        dy[0][i] = dy[0][i-1] + arr[0][i]
        dy[i][0] = dy[i-1][0] + arr[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]) + arr[i][j]
   

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

 

 

 

Point ! ⭐️

• dy 리스트를 만들어주고 정의를 해보면 dy[1][1]은 (1,1)까지 오는데 가장 적은 에너지로 오는 에너지의 양이 적혀 있다. 
  arr[0][0]에서 arr[n-1][n-1] 까지 가는 길 중 최소 에너지를 들여 가야하기 때문에 일단 이동은 오른쪽이나 아래쪽으로 밖에 움직이지 못한다. 아니면 돌아가기 때문에 !
  그렇게 되면 0행에 있는 예를 들어 arr[0][3]은 arr[0][2]에서 밖에 못오기 때문에 왼쪽에서 밖에 못온다. 
  또한 0열에 있는 것들을 arr[2][0]은 arr[1][0]에서 밖에 못오기 때문에 위쪽에서 밖에 못온다.
  그래서 맨 처음 0행과 0열은 그 전의 값을 더해주며 값을 dy 리스트에 넣어둔다. 
  
  dy[1][1]에서부터 값을 넣어주는데 dy[1][1]은 dy[1][0]에서 오거나 dy[0][1]에서 오니까 위쪽 또는 왼쪽에서 오는 값 중 가장 적은 에너지의 값과 자신의 값을 더해줘야하는 것이다. 
  dy[1][1] = min(dy[0][1], dy[1][0]) + arr[1][1] 이 되는 것이다 !

 

 

 

 

 

 

출처

• 인프런 : 파이썬 알고리즘 문제 풀이