1444. Number of Ways of Cutting a Pizza

[zeikar]

Problem link

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

Problem Summary

사과가 올려져 있는 피자가 있을 때 사과가 1개 이상 올라가 있도록 피자를 k개로 나누는 경우의 수를 구하는 문제.
피자는 행 또는 열로 죽 자를 수 있다.

Solution

딱 보니 모듈러도 있고 자른 모양이 DP 할 수 있게 생겼다.
점화식을 간단히 만들면

DP[i][j][k] = 행으로 i번, 열로 j번 자를 때 k 개 조각으로 나눌 수 있는 경우의 수

여기까지는 간단한데 사과 개수가 최소 1개 이상 있어야 한다.
입력 크기가 작아서 무식하게 O(nm) 돌면서 사과 개수를 세어줘도 충분히 돌아간다.

2d prefix sum을 이용하면 사과 개수를 O(1)로 구할 수 있고 좀 빨라지긴 한다.

Source Code

O(n^2 m^2 k) - 2497 ms

from functools import lru_cache
from typing import List


class Solution:
    def ways(self, pizza: List[str], k: int) -> int:

        rows = len(pizza)
        cols = len(pizza[0])

        @lru_cache(None)
        def solve(top: int, left: int, pieces: int):
            if pieces == 0:
                apple_cnt = 0
                for i in range(top, rows):
                    for j in range(left, cols):
                        if pizza[i][j] == 'A':
                            apple_cnt += 1
                return 1 if apple_cnt > 0 else 0
            if top == rows or left == cols:
                return 0

            cut_top = 0
            apple_cnt = 0
            for i in range(top, rows):
                for j in range(left, cols):
                    apple_cnt += 1 if pizza[i][j] == 'A' else 0

                if apple_cnt > 0:
                    cut_top += solve(i + 1, left, pieces - 1)

            cut_left = 0
            apple_cnt = 0
            for j in range(left, cols):
                for i in range(top, rows):
                    apple_cnt += 1 if pizza[i][j] == 'A' else 0

                if apple_cnt > 0:
                    cut_left += solve(top, j + 1, pieces - 1)

            return (cut_top + cut_left) % (10 ** 9 + 7)

        return solve(0, 0, k - 1)

O(nm (n+m) k) - 991 ms

from functools import lru_cache
from typing import List


class Solution:
    def ways(self, pizza: List[str], k: int) -> int:

        rows = len(pizza)
        cols = len(pizza[0])

        apple_dp = [[0 for _ in range(cols)] for _ in range(rows)]
        for i in range(rows):
            for j in range(cols):
                apple_dp[i][j] += apple_dp[i - 1][j] if i > 0 else 0
                apple_dp[i][j] += apple_dp[i][j - 1] if j > 0 else 0
                apple_dp[i][j] -= apple_dp[i - 1][j - 1] if i > 0 and j > 0 else 0
                apple_dp[i][j] += 1 if pizza[i][j] == 'A' else 0

        def count_apple(top, left, bottom, right):
            cnt = apple_dp[bottom][right]
            cnt -= apple_dp[bottom][left - 1] if left > 0 else 0
            cnt -= apple_dp[top - 1][right] if top > 0 else 0
            cnt += apple_dp[top - 1][left - 1] if top > 0 and left > 0 else 0
            return cnt

        @lru_cache(None)
        def solve(top: int, left: int, pieces: int):
            if pieces == 0:
                return 1 if count_apple(top, left, rows - 1, cols - 1) > 0 else 0
            if top == rows or left == cols:
                return 0

            cut_top = 0
            for i in range(top, rows):
                if count_apple(top, left, i, cols - 1) > 0:
                    cut_top += solve(i + 1, left, pieces - 1)

            cut_left = 0
            for j in range(left, cols):
                if count_apple(top, left, rows - 1, j) > 0:
                    cut_left += solve(top, j + 1, pieces - 1)

            return (cut_top + cut_left) % (10 ** 9 + 7)

        return solve(0, 0, k - 1)