[LeetCode] 1289. Minimum Falling Path Sum II (Daily Question)

문제

---

Given an n x n integer matrix grid, return the minimum sum of a falling path with non-zero shifts.

A falling path with non-zero shifts is a choice of exactly one element from each row of grid such that no two elements chosen in adjacent rows are in the same column.

 

2차원 배열 grid가 주어졌을 때, 맨 위(0행)에서 내려가면서 더했을 때 만들 수 있는 최솟값을 구하는 문제이다.

단, 내려갈 때는 같은 열로 내려갈 수 없다. 

 

Example 1:
Input: grid = [[1,2,3],[4,5,6],[7,8,9]]
Output: 13
Explanation: The possible falling paths are: [1,5,9], [1,5,7], [1,6,7], [1,6,8], [2,4,8], [2,4,9], [2,6,7], [2,6,8], [3,4,8], [3,4,9], [3,5,7], [3,5,9] The falling path with the smallest sum is [1,5,7], so the answer is 13.

Example 2:
Input: grid = [[7]]
Output: 7

 

풀이

---

아이디어

- 현재 행의 제일 작은 값 및 열 번호, 두 번째로 작은 값을 구한다.

- 다음 행의 모든 값에 제일 작은 값을 다 더해주는데, 같은 열 번호는 두 번째로 작은 값을 더해준다.

- 반복

 

 

코드

class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        min1 = (100, -1)
        min2 = (100, -1)

        for i in range(len(grid)):
            min3 = (100*200, -1)
            min4 = (100*200, -1)
            
            for j in range(len(grid[0])):
                # i가 0일때는 최소값을 더해줄 필요X
                if i!= 0:
                    if min1[1] != j:
                        grid[i][j] += min1[0]
                    else:
                        grid[i][j] += min2[0]

                # 행의 최소값
                if min3[0] > grid[i][j]:
                    min4 = min3
                    min3 = (grid[i][j], j)
                # 행의 두 번째로 작은 값
                elif min4[0] > grid[i][j]:
                    min4 = (grid[i][j], j)

            min1 = min3
            min2 = min4

        return min1[0]

 

---

 

후기

---

아이디어만 떠올린다면 풀만한 문제이다.

예외사항도 딱히 없어서 Hard문제 치고는 쉬웠다.