행렬분할 2

• 입력값들의 제한을 살펴보면 m의 범위가 8이하로 굉장히 작다. 세로 방향의 분할방법은 전부 해봤자 C(m-1, b)개 밖에 안되고, 이 모든 경우를 다 시도해봐도 무리가 없다.
• 세로방향의 분할을 고정시킨 다음, 가로방향의 분할을 결정하는 것은 파라메트릭 서치를 사용하면 된다. 1차원 배열을 부분합의 최댓값을 최소화하도록 분할하는 것은 파라메트릭 서치의 흔한 사용패턴중 하나인데, 이 테크닉을 여러개의 1차원 배열로 확장시켰을뿐 특별히 다른것은 없다.
• 최댓값을 고정시켜놓고, 그 최댓값 이하로 가로 분할이 가능한지 아닌지 확인하는 것은 O(n*m)이 걸린다. 최댓값을 탐색할 범위의 상한을 간단하게 모든 행렬값의 합으로 지정한다면, 탐색 횟수는 O(log(n*m*K)) 이고 (K는 행렬의 원소의 최댓값 =100,000), 파라메트릭 서치에 걸리는 총 시간복잡도는 O(nmlog(nmC))가 된다.
• 이 파라메트릭 서치를 총 모든 세로분할 방법에 대해서 시도해서 그중에서 최솟값을 찾아야 하므로, 총 시간복잡도는 O(C(m-1,b)*nmlog(nmK)) 가 된다. b를 빼고 생각하고 싶으면, 그냥 O(2^m*nmlog(nmK))로 쓰자.
• 아이디어는 심플한데 구현은 좀 번거롭다.
• 사소한 속도 향상 팁은, 세로 분할을 고정시켰을때, 그 분할에 대한 행렬을 미리 O(m*n)으로 계산해놓으면, 파라메트릭 서치 안에서 가로 분할이 가능한지 체크하는 것은 O(n*m)대신 O(n*b)로 할수 있다. 맨 처음에 행렬의 각 열마다 누적합을 구해 놓으면, 세로분할마다 O(mn)을 계산하는것조차 필요없긴 한데.. 거기까지는 구현 안했다.

"""Solution code for "BOJ 23331. 행렬분할 2".

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

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