[LeetCode] Medium - 931 Minimum Falling Path Sum (Python)

▶931 - Minimum Falling Path Sum

▶문제

Given an n x n array of integers matrix, return the minimum sum of any falling path through matrix.

A falling path starts at any element in the first row and chooses the element in the next row that is either directly below or diagonally left/right. Specifically, the next element from position (row, col) will be (row + 1, col - 1), (row + 1, col), or (row + 1, col + 1).

 

▶예제

Input: matrix = [[2,1,3],[6,5,4],[7,8,9]]
Output: 13
Explanation: There are two falling paths with a minimum sum as shown.

Input: matrix = [[-19,57],[-40,-5]]
Output: -59
Explanation: The falling path with a minimum sum is shown.

728x90

▶풀이

dp를 이용하는 문제이다.

필요한 칸의 개수만큼 dp를 만들어 준 다음에, 위에서 올 수 있는 모든 경우 중 최솟값을 가지고 온다.

양 끝 배열의 경우 2개, 가운데 배열은 3개의 값을 가지고 비교해주면 된다.

그다음에 현재 matrix의 값과 더해서 넣어준다.

 

마지막 줄에서의 min값을 return 해주면 된다.

 

medium문제지만, 백준으로 치면 실버 정도에 문제인 것 같다.

다른 사람들도 크게 어려움을 겪지 않을 거 같다.

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        dp = [[0 for _ in range(len(matrix))] for _ in range(len(matrix))]
        for i in range(len(matrix)):
            dp[0][i] = matrix[0][i]
        for i in range(1, len(matrix)):
            for j in range(len(matrix)):
                if j == 0:
                    dp[i][j] = min(dp[i - 1][j], dp[i - 1][j + 1]) + matrix[i][j]
                elif j == len(matrix) - 1:
                    dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + matrix[i][j]
                else:
                    dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1], dp[i - 1][j + 1]) + matrix[i][j]
        return min(dp[len(matrix) - 1])

이렇게 풀면 쉽게 풀릴 것이다.

runtime의 경우 생각보다 낮게 나왔는데, 이 부분은 좀 생각해봐야 할 것 같다.