📍무제
양수로 이루어진 m x n 그리드를 인자로 드립니다. 상단 왼쪽에서 시작하여, 하단 오른쪽까지 가는 길의 요소를 다 더했을 때,가장 작은 합을 찾아서 return 해주세요.
한 지점에서 우측이나 아래로만 이동할 수 있습니다.
Input | Output |
---|---|
[ [1,3,1], [1,5,1], [4,2,1] ] | 7 |
설명: 1→3→1→1→1 의 합이 제일 작음
def min_path_sum(grid):
for i in range(1,len(grid)): # 세로 한칸씩 더한 값 저장
grid[i][0] += grid[i-1][0]
for i in range(1,len(grid[0])): # 가로 한칸씩 더한 값 저장
grid[0][i] += grid[0][i-1]
for i in range(1, len(grid[0])): # 가로 길이
for j in range(1, len(grid)): # 세로길이
grid[i][j] += min(grid[i-1][j], grid[i][j-1]) # 위쪽,왼쪽 중 작은 값 더하기
return grid[-1][-1] # 덧셈이 모두 끝난 후 마지막 값 반환