백준 12001 Load Balancing (USACO February 2016 Bronze 3번)

문제 링크: https://www.acmicpc.net/problem/12001

12001번: Load Balancing (Bronze)

N개 점들의 x좌표, y좌표들 사이에 가능한 모든곳에 fence를 놓고, 나뉘어진 4개 각각 region에 있는 점들의 수의 maximum인 M 을 찾고, 그 M값들의 최소값을 찾음. 시간 복잡도는 O(N^3)이고, N의 최대값이 100이기에 충분히 빠른시간내에 돌아감.

#include <bits/stdc++.h>
using namespace std;
 
int N, B;
vector<pair<int, int>> pos;
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> N >> B;
    for(int i = 0; i < N; i++) {
        int x, y;
        cin >> x >> y;
        pos.push_back({x, y});
    }
 
    int ans = 1e9;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            int a = pos[i].first + 1, b = pos[j].second + 1;
            int cnt[4] ={};
            for(int k = 0; k < N; k++) {
                int x = pos[k].first, y = pos[k].second;
                if(x > a && y > b) cnt[0]++;
                else if(x < a && y > b) cnt[1]++;
                else if(x > a && y < b) cnt[2]++;
                else cnt[3]++;
            }
            int M = 0;
            for(int k = 0; k < 4; k++)
                M = max(M, cnt[k]);
            ans = min(ans, M);
        }
    }
 
    cout << ans << '\n';
    return 0;
}