5842번: Partitioning the Farm

https://www.acmicpc.net/problem/5842

먼저 가로 방향 울타리의 위치를 정한다. 여기서 가능한 모양의 경우의 수는 $2^{n-1}$일 것이다.
그 다음, 남은 울타리를 세로 방향으로 설치하되 그룹 안 소의 최대 수가 최소가 되도록 설치하는 법을 찾아야 한다.
그룹 안 소의 최대 수를 x라고 하고 이 값에 대해 파라메트릭 서치를 한다. 농장의 왼쪽 열부터 보면서 그룹 안 소의 최대 수가 x이하가 되도록 세로로 울타리를 세웠을 때 모든 울타리 수가 k개 이하인지 판단하는 문제로 바꿔 풀 수 있다.

시간복잡도는 $O(2^{n/2}*n^2*\lg L)$

#include<cstdio>
int n, k, s[16][16], a[16], sz, mid, res = 1e9;
bool f() {
    int t = 0, cnt = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= sz; j++) while (s[a[j]][i] - s[a[j]][t] - s[a[j - 1]][i] + s[a[j - 1]][t] > mid) {
            if (t == i - 1) return false;
            t = i - 1, cnt++;
        }
    }
    return cnt <= k - sz + 1;
}
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) {
        scanf("%d", s[i] + j);
        s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
    }
    for (int i = 1 << n - 1; i--;) {
        sz = 0;
        for (int j = 0; j < n - 1; j++) if (1 << j&i) a[++sz] = j + 1;
        a[++sz] = n;
        int low = 0, up = 1e6;
        while (low <= up) {
            mid = low + up >> 1;
            f() ? up = mid - 1 : low = mid + 1;
        }
        if (res > up) res = low;
    }
    printf("%d", res);
    return 0;
}