931. Minimum Falling Path Sum

931. Minimum Falling Path Sum

 

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        # nxn 배열
        # 3방향으로 떨어질수 있음. => 3방향으로 올라갈수 있다는 의미
        # 계산 다해서, 제일 윗 열중, 최소값 찾으면 됨
        N = len(matrix)

        # 이것도 역순으로.. 아래에서->위로, 
        # 그런데, 제일 아래줄은 계산에는 반영해도
        # 루프에는 빼기        
        for r in range(N-2, -1, -1):
            for c in range(N):
                if c == 0:
                    matrix[r][c] += min(matrix[r+1][c], matrix[r+1][c+1])
                elif c == N-1:
                    matrix[r][c] += min(matrix[r+1][c-1], matrix[r+1][c])
                else:
                    matrix[r][c] += min(matrix[r+1][c-1], matrix[r+1][c], matrix[r+1][c+1])

        return min(matrix[0][:])

 

1차: 2025.01.03 그냥 품