문제

양수로 이루어진 m x n 그리드를 인자로 드립니다.
상단 왼쪽에서 시작하여, 하단 오른쪽까지 가는 길의 요소를 다 더했을 때,가장 작은 합을 찾아서 return 해주세요.

한 지점에서 우측이나 아래로만 이동할 수 있습니다.

Input:

[
 [1,3,1],
 [1,5,1],
 [4,2,1]
]

Output: 7

설명: 1→3→1→1→1 의 합이 제일 작음

Solution

일단 grid[0][0]에서 시작해서 가로 세로 까지의 합을 다 구한다. (무조건 최단거리이기 때문에)

m = len(grid) # 그리드의 세로길이
n = len(grid[0]) # 그리드의 가로길이

그래서 해당 index의 값을 grid[0][0]에서 해당 index까지의 합으로 바꿔준다.

ex)

[
 [1,4,5],
 [2,5,1],
 [6,2,1]
]

그 뒤 grid[1][1] ~ grid[-1][-1]까지 하나씩 비교(최단거리)해가면서 해당 index를 합으로 바꿔준다.

ex)

[
 [1,4,5],
 [2,7,1],   # 여기서 grid[1][1]인 5까지의 최단거리를 
 [6,2,1]      grid[0][1]과 grid[1][0]을 비교하여 낮은 값을 더하는 방법
]                          그렇게 되면, 5에 2와 4중 낮은값인 2를 더해 7이 됨

그리하여 최종적으로 바뀐 grid[-1][-1]의 값이 최소의 합이 됨

def min_path_sum(grid):
    m = len(grid)
    n = len(grid[0])
    for i in range(1, n):
        grid[0][i] += grid[0][i-1]
    for i in range(1, m):
        grid[i][0] += grid[i-1][0]
    for i in range(1, m):
        for j in range(1, n):
            grid[i][j] += min(grid[i-1][j], grid[i][j-1])
    return grid[-1][-1]