행렬분할

• 행렬분할 2의 쉬운 버전. 행렬분할 2에서는 n이 최대 100이라서 파라메트릭 서치를 사용해야만 했는데, 여기에서는 그냥 백트래킹으로 다 해봐도 답을 구할 수 있는것 같다. 하지만, 그렇게 구현하지는 않았고, 그냥 행렬분할 2의 코드를 그대로 재사용했다.
• 풀이는 행렬분할 2 참고.

"""Solution code for "BOJ 23318. 행렬분할".

- Problem link: https://www.acmicpc.net/problem/23318
- Solution link: http://www.teferi.net/ps/problems/boj/23318

Tags: [Parametric search]
"""

import itertools
import functools
from teflib import binsearch

INF = float('inf')


def can_divide(sum_limit, remaining_div_count, mat):
    sums = [0] * (len(mat[0]))
    for nums in mat:
        sums = [s + n for s, n in zip(sums, nums)]
        if any(s > sum_limit for s in sums):
            if any(n > sum_limit for n in nums):
                return False
            sums = nums
            remaining_div_count -= 1
            if remaining_div_count < 0:
                return False
    return True


def main():
    n, m = [int(x) for x in input().split()]
    a, b = [int(x) for x in input().split()]
    mat = [[int(x) for x in input().split()] for _ in range(n)]

    all_sum = sum(sum(row) for row in mat)
    answer = INF
    for partition in itertools.combinations(range(1, m), b):
        partition = (0, *partition, m)
        new_mat = [[
            sum(row[beg:end]) for beg, end in itertools.pairwise(partition)
        ] for row in mat]
        pred = functools.partial(can_divide, remaining_div_count=a, mat=new_mat)
        min_score = binsearch.minimum_valid_integer(0, all_sum, pred)
        answer = min(answer, min_score)

    print(answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.binsearch.minimum_valid_integer