BOJ 12001 · Load Balancing (Bronze)

알고리즘 분류 : 브루트 포스  

농장을 4군데로 분할하여, 가장 균형 있게 나누는 방법을 푸는 문제다. 균형 있게 나눈다는 것은 4군데 중 어느 한곳에 너무 많은 소가 배치되지 않도록 나누는 것을 말한다. N이 최대 100이므로, 모든 경우의 수를 만들어도 해결할 수 있다.

• X축 기준을 정하고 위아래로 나눈다.
• Y축 기준을 정하고 양옆으로 나눈다.
• 각 지역에 존재하는 소가 몇 마리인지 센다.
• 위에서 센 소의 수 중, 가장 큰 값을 cow라고 하자.
• N*N 번 반복하면서 얻을 수 있는 cow 중, 가장 작은 값이 정답이다.

---

C++ 소스코드

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
vector<int> x, y;

void solve() {
    int ans = 1e9;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            int a = 0, b = 0, c = 0, d = 0;
            for (int k=0; k<n; k++) {
                if (x[k] < x[i]+1 && y[k] < y[j]+1) a++;
                if (x[k] < x[i]+1 && y[k] > y[j]+1) b++;
                if (x[k] > x[i]+1 && y[k] < y[j]+1) c++;
                if (x[k] > x[i]+1 && y[k] > y[j]+1) d++;
            }
            int cow = max(max(max(a, b), c), d);
            if (ans > cow) ans = cow;
        }
    }
    printf("%d\n", ans);
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i=0; i<n; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        x.push_back(a);
        y.push_back(b);
    }
    solve();
    return 0;
}

---

Python 3 소스코드

from sys import stdin
input = stdin.readline

n, m = map(int, input().split())
x, y = [[] for _ in range(n)], [[] for _ in range(n)]
for i in range(n):
    x[i], y[i] = map(int, input().split())

def solve():
    ans = 1e9
    for i in range(n):
        for j in range(n):
            a, b, c, d = [0]*4
            for k in range(n):
                if x[k] < x[i]+1 and y[k] < y[j]+1:
                    a += 1
                if x[k] < x[i]+1 and y[k] > y[j]+1:
                    b += 1
                if x[k] > x[i]+1 and y[k] > y[j]+1:
                    c += 1
                if x[k] > x[i]+1 and y[k] < y[j]+1:
                    d += 1
            gap = max(a, b, c, d)
            ans = min(ans, gap)
    print(ans)

solve()

---

참고

• 백준 온라인 저지 : BOJ 12001