Code Kata | day13 min_path_sum

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

☑️ code

리스트를 아래로 쌓는다. m은 가로길이, n은 세로길이가 된다. 아래 보이는 그림과 같이 우측 혹은 아래쪽에 있는 값을 더한 누적값 그대로 이동한다고 생각하면 쉽다. (4 = 1 + 3, 5 = 4 + 1 이때 4는 동일한 4이다. )

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-1][j], grid[i][j-1])
  
  return grid[-1][-1]
  

Review
이런 알고리즘 문제는 새로운 함수나 메소드를 사용하는 것보다 답을 찾는 방법을 생각해내는게 어렵다. 최대한 많이 접하고 새로운 방법을 생각하는 방식 자체를 훈련하는 게 중요하다.