티스토리 뷰

알고리즘 관련/BOJ

BOJ)5842 Partitioning the Farm

JASON 자손9319 2017. 9. 7. 02:48

문제: icpc.me/5842


n*n 격자가 주어질 때 주어진 격자를 가로나 세로로 k번 분할 할 수 있다.


분할 된 각 부분들의 합의 최댓값의 최솟값을 구하는 문제이다.


최대중에 최소를 구하는 문제이므로 파라메트릭 서치로 접근할 수 있다.


다만 격자에서 처리해야하는게 좀 까다로울 수 있는데


n이 15밖에 안되므로 2^15의 모든 경우로 세로 격자를 세워준 뒤 파라메트릭 서치로 가로 격자를 세우며 답을 구할 수 있다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n, k, a[16][16], x[16], res, y[16][16], z[16];
int main() {
    scanf("%d%d"&n, &k);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            scanf("%d"&a[i][j]);
    }
    res = 1e9;
    for (int i = 0; i < (<< n); i++) {
        int hcnt = 0;
        memset(x, 0sizeof(x));
        memset(y, 0sizeof(y));
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                x[k] += a[k][j];
                if ((<< j)&i) {
                    y[k][hcnt] = x[k];
                    x[k] = 0;
                }
            }
            if ((<< j)&i)hcnt++;
        }
        for (int k = 0; k < n; k++) {
            y[k][hcnt] = x[k];
            x[k] = 0;
        }
        int diff = k - hcnt;
        hcnt++;
        int lo = 0;
        int hi = n * n * 1001;
        while (lo < hi) {
            int cnt = 0;
            int mid = (lo + hi) >> 1;
            memset(z, 0sizeof(z));
            for (int j = 0; j < n; j++) {
                int f = 0;
                for (int k = 0; k < hcnt; k++) {
                    if (y[j][k]>mid) {
                        cnt = 1e9;
                        break;
                    }
                    else if (y[j][k] + z[k]>mid)
                        f = 1;
                    else
                        z[k] += y[j][k];
                }
                if (cnt == 1e9)break;
                if (f) {
                    cnt++;
                    for (int k = 0; k < hcnt; k++)
                        z[k] = y[j][k];
                }
            }
            if (cnt > diff)
                lo = mid + 1;
            else
                hi = mid;
        }
        res = min(res, lo);
    }
    printf("%d\n", res);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)13330 유사 팰린드롬  (0) 2017.09.08
BOJ)13352 석양이 진다...  (1) 2017.09.07
BOJ)5842 Partitioning the Farm  (0) 2017.09.07
BOJ)2337 트리 자르기  (1) 2017.09.05
BOJ)11003 최소값 찾기  (1) 2017.09.05
BOJ)1460 진욱이의 농장  (0) 2017.09.05
댓글
댓글쓰기 폼