문제
양수로 이루어진 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]
- 코드 리뷰
1) 먼저 grid[0][i]들의 값과 grid[i][0]값들의 합을 먼저 구하는 방법이 매우 기발했다.
2) 이후 값들은 이중 for문을 통해서 이전 index들의 min값과 현재 값의 합을 통해 간단하게 구할 수 있었다.