[백준/C++] 11997번: Load Balancing (Silver)(G4)

 

문제

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

11997번: Load Balancing (Silver)

 

사용한 알고리즘

• 2022.02.02 - [PS/Algorithm] - [알고리즘 개념정리] 7. 이분탐색/분할정복

-> 좌표압축

• 누적 합

 

 

문제 설명

좌표평면에 있는 소의 위치(양의 홀수, 양의 홀수)가 주어진다.
x=a, y=b에 울타리를 친다. (a와 b는 양의 짝수)

그러면 (a,b)를 기준으로 4구역으로 나뉘는데
네 구역에서 소가 가장 많은 곳의 수를 최소화하는 (a,b)를 찾으면 된다.

 

 

풀이

알고리즘 분류 태그에는 '누적 합' 만 되어있지만
소의 위치 범위가 10^6 * 10^6이므로 좌표 압축도 써서 풀어야한다.

먼저 소의 실제 위치를 배열 x와 배열 y에 받아준다.
각각을 px와 py 벡터에 넣어주고 정렬 후 중복 원소를 제거해준다.

x[i]와 y[i]를 각각 px와 py에서의 인덱스로 좌표압축 해준 후
mat[x[i]][y[i]]를 1로 만들어준다.

이제 (a,b)를 기준으로 만들어지는 4구역들을 보며 답을 찾으면 된다.
이중for문을 돌면서 (a,b)를 지정하고 4구역에 포함된 소들(mat[i][j])을 또 순회하며 더하면 시간초과가 난다.
그래서 2차원 누적합 배열 sum을 사용했다.

sum[i][j]는 sum[0][0]부터 sum[i][j]까지의 mat[][]의 누적 합이다.
이중for문을 돌며 sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+mat[i][j]을 하면 된다.
 
sum을 다 채우면 이제 정답을 구한다.
이중for문을 돌며 (a,b)로 나눠지는 4구역에서 소의 합 max를 구한다.
왼쪽 위 구역은 sum[i][j],
왼쪽 아래 구역은 sum[n-1][j]-sum[i][j],
오른쪽 위 구역은 sum[i][n-1]-sum[i][j],
오른쪽 아래 구역은 sum[n-1][n-1]-sum[n-1][j]-sum[i][n-1]+sum[i][j] 이다.

구해진 max값들 중 최솟값을 출력하면 된다.

 

 

소스코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long ll;
int n;
int x[1001],y[1001],mat[1001][1001];
vector<int>px,py; //중복제거
int sum[1001][1001];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin>>n;
    for(int i=0; i<n; i++){
        cin>>x[i]>>y[i]; //실제 좌표 입력받기
        px.push_back(x[i]);
        py.push_back(y[i]);
    }
    //좌표압축을 위해 중복제거
    sort(px.begin(), px.end());
    px.erase(unique(px.begin(),px.end()),px.end());
    sort(py.begin(), py.end());
    py.erase(unique(py.begin(),py.end()),py.end());

    for(int i=0; i<n; i++){
        //좌표압축
        x[i]=lower_bound(px.begin(), px.end(), x[i]) - px.begin();
        y[i]=lower_bound(py.begin(), py.end(), y[i]) - py.begin();
        mat[x[i]][y[i]]++; //좌표압축한 좌표 기준으로 cow있으면 mat[i][j]=1
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            //sum에다가 mat의 누적합 저장
            //sum[i][j]는 sum[0][0]~sum[i][j]의 mat누적합
            if(!i&&!j) sum[i][j]=mat[i][j];
            else if(!i) sum[i][j]= sum[i][j-1]+mat[i][j];
            else if(!j) sum[i][j] = sum[i-1][j]+mat[i][j];
            else sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+mat[i][j];
        }
    }

    int ans=n; //네 구역의 cow수 MAX를 최소화한 값
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            //(i,j)는 fence (a,b)를 의미함
            int part = sum[i][j]; //왼쪽위 구역
            part=max(part, sum[n-1][n-1]-sum[n-1][j]-sum[i][n-1]+sum[i][j]); //오른쪽아래 구역
            part=max(part, sum[n-1][j]-sum[i][j]); //왼쪽아래 구역
            part=max(part, sum[i][n-1]-sum[i][j]);//오른쪽위 구역
            ans=min(ans,part);
        }
    }
    cout<<ans;
    return 0;
}