2023.03.31 Today's Challenge

https://leetcode.com/problems/number-of-ways-of-cutting-a-pizza/

Number of Ways of Cutting a Pizza - LeetCode

조금 난이도가 있는 DP 문제!

class Solution:
    def ways(self, pizza: List[str], k: int) -> int:
        rows, cols = len(pizza), len(pizza[0])
        apples = [[0] * (cols + 1) for row in range(rows + 1)]
        for row in range(rows-1, -1, -1):
            for col in range(cols-1, -1, -1):
                apples[row][col] = ((pizza[row][col] == 'A')
                + apples[row+1][col] + apples[row][col+1] - apples[row+1][col+1])
        
        dp = [[[0 for col in range(cols)] for row in range(rows)] for remain in range(k)]
        dp[0] = [[int(apples[row][col] > 0) for col in range(cols)] for row in range(rows)]
        mod = 1000000007

        for remain in range(1, k):
            for row in range(rows):
                for col in range(cols):
                    val = 0
                    for next_row in range(row+1, rows):
                        if apples[row][col] - apples[next_row][col] > 0:
                            val += dp[remain - 1][next_row][col]
                    for next_col in range(col+1, cols):
                        if apples[row][col] - apples[row][next_col] > 0:
                            val += dp[remain - 1][row][next_col]
                    dp[remain][row][col] = val % mod
        
        return dp[k-1][0][0]