leetcode hard : Paths in Matrix Whose Sum Is Divisible by K

https://leetcode.com/problems/paths-in-matrix-whose-sum-is-divisible-by-k/

 

k로 나눠 떨어지는 path의 개수를 세라는건데

k로 나눈다는 조건이 없으면 그냥 우리가 어릴때 배웠던 길 개수 세기랑 똑같다.

문제는 m-1, n-1에 도달하기 전까진 끝에서 k로 나눴을때 remainder가 얼마나될지 알수가 없다는 것이다.

 그래서 특정 remainder의 path개수가 얼마나 되는지 실시간으로 카운트하고

마지막에 remainder가 0인 path개수를 리턴하면 된다.

class Solution:
    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[[0] * k for _ in range(n)] for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if i == 0 and j == 0:
                    dp[0][0][grid[0][0] % k] += 1
                    continue
                if i == 0:
                    for mod in range(k):
                        dp[i][j][(mod + grid[i][j]) % k] += dp[i][j-1][mod] % (10 ** 9 + 7)
                    continue
                if j == 0:
                    for mod in range(k):
                        dp[i][j][(mod + grid[i][j]) % k] += dp[i-1][j][mod] % (10 ** 9 + 7)
                    continue
                for mod in range(k):
                    dp[i][j][(mod + grid[i][j]) % k] += dp[i][j-1][mod] % (10 ** 9 + 7)
                    dp[i][j][(mod + grid[i][j]) % k] += dp[i-1][j][mod] % (10 ** 9 + 7)
        
        return dp[m - 1][n - 1][0] % (10 ** 9 + 7)