[알고리즘] 알리바바와 40인의 도둑(Bottom-Up)

(문제) 알리바바와 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)도착지로 가기 위한 최소 에너지를 출력한다.

테스트케이스

입력예제	출력예제
3 3 3 5 2 3 4 6 5 2	14
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	25
10 9 4 6 7 5 1 3 1 5 3 2 4 6 3 9 8 9 1 3 2 6 9 6 2 4 1 8 3 7 8 3 9 7 5 3 1 3 6 6 1 3 6 6 3 8 9 6 7 7 4 1 4 5 3 1 8 1 9 1 3 7 3 1 1 7 7 3 7 4 3 8 5 6 7 7 9 1 8 3 2 2 8 7 4 3 4 2 9 2 9 1 1 1 2 6 1 3 8 1 9	69

---

해결방법

동작 시각화

---

코드

n = int(input())

rocks = [list(map(int, input().split())) for _ in range(n)]

# 좌표도 2차원으로
dt = [[0] * n for _ in range(n)]


# 시작하는 것 초기화
for i in range(n):
    if i - 1 < 0:
        dt[0][i] = rocks[0][i]
        dt[i][0] = rocks[i][0]
    else:
        dt[0][i] = dt[0][i-1] + rocks[0][i]
        dt[i][0] = dt[i-1][0] + rocks[i][0]

# 왼쪽 확인 위쪽 확인
# 전의 것을 확인하기 위해서
dx = [0, -1]
dy = [-1, 0]

# 적냐 크냐
# 적으면 적은곳으로 간다
# 그곳의 좌표를 이용해서 또한다
for i in range(1, n):
    for j in range(1, n):
        _min = 2174000000
        # 위쪽, 왼쪽 보기
        for k in range(2):
            if _min > dt[i + dy[k]][j + dx[k]]:
                _min = dt[i + dy[k]][j + dx[k]]

        dt[i][j] = _min + rocks[i][j]


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