문제
양수로 이루어진 m x n 그리드를 인자로 드립니다.
상단 왼쪽에서 시작하여, 하단 오른쪽까지 가는 길의 요소를 다 더했을 때,가장 작은 합을 찾아서 return 해주세요.
한 지점에서 우측이나 아래로만 이동할 수 있습니다.
Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7설명: 1→3→1→1→1 의 합이 제일 작음
Model Solution
def minPathSum(grid):
m = len(grid)
n = len(grid[0])
### 1
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]
### 2
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] 어떻게 풀어나갈지 모르겠어서 그냥 답을 보고 이해하기로 했다.
주어진 조건은 그리드 내에서는 오른쪽, 아래로만 이동 가능하고 가장 최소의 합을 찾아내야 한다는 것이다. 그렇기때문에 이동할때마다 계속 최소의 합이 무엇인지 추적해야한다.
그냥 생각하면 오른쪽과 아래쪽으로만 이동한다고 해도 수 많은 경우의 수가 있을것인데 이 합들을 다 어떻게 쫒아갈지 막막하기때문에 합을 어떻게 추적할지에 대해서 좀 더 고민해봐야한다.
항상 오른쪽, 아래로만 이동하기 때문에 한 요소까지의 합을 구하려면 해당 요소의 왼쪽과 위의 요소에서 지금까지의 합을 알려주어야 현재 요소의 값과 더해줄 수 있다. 즉, 한 요소의 왼쪽과 위는 항상 지금까지의 합산 값을 다음 값에게 제공해주어야 한다. 그게 바로 #2의 설명이다.
하지만 가장 왼쪽과 위의 요소는 한 방향밖에 없으므로 그 부분부터 먼저 합을 구해주어야 한다.(#1)
정리하면, 합이 만들어져야하는 가장 마지막인 grid[-1][-1]를 제외하고 모든 좌표에서 합이 구해져야한다. 그냥 무작위로 구하는게 아니라 일단 가장 왼쪽과 가장 위의 요소들의 합이 준비되어야하고 그 합이 준비 되어 있어야 오른쪽 아래의 요소들이 합을 구할 수 있다. 이렇게 왼쪽과 위의 값들이 모두 합으로 바뀐 요소는 합을 업데이트 할 수 있다.
