[인프런] 알리바바와 40인의 도둑

---

문제설명

알이바바는 40인의 도둑으로부터 금화를 훔쳐 도망치고 있다. 알리바바는 도망치는 길에 평소에 잘 가지 않던 계곡의 돌다리로 도망가고자 한다. 계곡의 돌다리는 N by N개의 돌들로 구성되어 있다. 각 돌다리들은 높이가 서로 다르다. 해당 돌다리를 건널 때 돌의 높이 만큼 에너지가 소비된다. 이동은 최단거리 이동을 한다. 즉, 현재 지점에서 오른쪽 또는 아래쪽으로만 이동해야 한다.

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

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

 

 

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

입력조건

• 첫 줄에는 자연수 N(1 <= N <= 20)이 주어진다.
• 둘째 줄부터 계곡의 N by N 격자의 돌다리 높이(10보다 작은 자연수) 정보가 주어진다.

출력조건

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

사고과정

• for loop를 활용하는 Bottom-up 방식으로 풀이하는 것은 잘 구현했다. DP 테이블을 2차원 테이블로 구성한 뒤, 이동한 지점의 입장에서 왼쪽/위쪽에서 오는 것 중 최솟값과 자기 자신 값을 더하는 점화식을 구현하면 된다.
• 그런데 재귀 함수를 활용하는 Top-down 방식으로 풀이하는 방법은 스스로 구현하지 못했다.. 상태트리를 그리는 데는 애써 잘 했지만 코드로 옮기는 과정이 쉽지 않았다. 강의를 보고 배우게 되었다.

풀이

- Bottom-Up 방식

n = int(input())
arr = []
dp = []
for _ in range(n):
    data = list(map(int, input().split()))
    arr.append(data)
    dp.append(data)
MAX = int(1e8)
for i in range(n):
    for j in range(n):
        if i == 0 and j == 0:
            continue
        if i == 0:
            up = MAX
        else:
            up = dp[i-1][j]
        if j == 0:
            left = MAX
        else:
            left = dp[i][j-1]
        dp[i][j] = arr[i][j] + min(up, left)

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

- Top-Down 방식

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

def dfs(x, y):
    # cut-edge 시 메모제이션 활용
    if dp[x][y] != 0:
        return dp[x][y]
    if x == 0 and y == 0:
        return arr[x][y]
    else:
        if y == 0:  # 열이 0일 때, 위로만 쭉 가야됨
            dp[x][y] = dfs(x-1, y) + arr[x][y]  # -> 메모제이션으로 활용하기 위해 그 때 DP테이블에 기록!
        elif x == 0:  # 행이 0일 때, 왼쪽으로만 쭉 가야됨
            dp[x][y] = dfs(x, y-1) + arr[x][y]  # -> 메모제이션으로 활용하기 위해 그 때 DP테이블에 기록!
        else:
            dp[x][y] = min(dfs(x-1, y), dfs(x, y-1)) + arr[x][y] # -> 메모제이션으로 활용하기 위해 그 때 DP테이블에 기록!
        return dp[x][y]  # 메모제이션으로 DP에 등록한 후 return 해야함!

print(dfs(n-1, n-1))