마의 구간, 수요일의 위코드 코드카타 시간!

우리끼리 장난으로 한주의 중간이라서 수요일 문제가 제일 어렵다고 한 적이 있었는데, 아무래도 사실인 것 같다.

문제

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

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

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

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

정말 이해해 보려고 했는데.. 난 x, y 축으로 생각해야 하는 경우가 오면 뇌가 정지하는 것 같다
사고를 거부하는 기분이랄까...

우선 주말에 다시보기!

---

model solution

def minPathSum(grid):
    m = len(grid)
    n = len(grid[0])
    
    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]
        
    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]

이전에 x, y축으로 면적 구하는 문제도 그렇고, 이렇게 3차원 적으로 생각해야 하는 상황이 오면 머리가 굳는 것 같다.

아무튼, 모델 솔루션을 이해해보자면
어쨌든 모든 길의 시작은 첫번째 배열에서 이루어지기 때문에
배열 전체의 개수, 첫번째 배열의 길이를 기준으로 구하는 것 같다.