[CodeKata] 12. min_path_sum

문제

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

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

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

Output: 7

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

풀이

1. 문제의 조건 정리

1) 양수로 이루어진 m x n 그리드를 인자로 받는다(이중 리스트)
2) grid[0][0] 에서 시작해서 grid[-1][-1]까지 왔을 때의 최소의 합을 반환한다.
3) 오른쪽과 아래쪽으로만 이동할 수 있다.

2. 조건에 대한 코드 구현 방법

1) 움직일 때마다 이전 인덱스와 현재 인덱스에서의 값의 합을 구한다.
2) grid[0][i]의 값들과 grid[i][0]의 값들의 합을 먼저 구하고 나머지 값을 구한다.

3. 코드 구현

def min_path_sum(grid):
  m = len(grid[0])
  n = len(grid)

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

  return grid[-1][-1]

4. 코드 리뷰

1) 먼저 grid[0][i]들의 값과 grid[i][0]값들의 합을 먼저 구하는 방법이 매우 기발했다.
2) 이후 값들은 이중 for문을 통해서 이전 index들의 min값과 현재 값의 합을 통해 간단하게 구할 수 있었다.