백준 11997번 Load Balancing(Silver)

문제 링크입니다: https://www.acmicpc.net/problem/11997

kks227님이 친절하게 좌표 압축 기법을 설명해주셨기 때문에 풀 수 있었던 문제였습니다.

또한 같은 학교 학우인 degurii가 부연 설명해줬기 때문에 AC를 받을 수 있었습니다.

알고리즘은 아래와 같습니다.

1. 소가 위치할 수 있는 범위가 1,000,000 * 1,000,000이므로 이차원 배열로는 표현할 수 없습니다.

2. 따라서, 좌표 해쉬 맵과 이진 탐색 트리(set)을 이용하여 좌표를 오름차순으로 압축합니다.

3. 좌표를 압축한 순서대로 전처리를 진행합니다.

4. 울타리를 모든 가능한 구간에 세워보고 사분면에 있는 소의 최대 수가 최소가 되는 지점을 업데이트합니다.

#include <iostream>

#include <algorithm>

#include <set>

#include <unordered_map>

using namespace std;

 

const int MAX = 1000 + 1;

 

int arr[MAX][MAX], pSum[MAX][MAX];

int y[MAX], x[MAX];

//좌표 압축을 위해

unordered_map<int, int> yHash, xHash;

set<int> ySet, xSet;

 

int func(int y, int x, int y2, int x2)

{

        return pSum[y2][x2] - pSum[y2][x] - pSum[y][x2] + pSum[y][x];

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N;

        cin >> N;

 

        for (int i = 0; i < N; i++)

        {

                 cin >> y[i] >> x[i];

 

                 ySet.insert(y[i]);

                 xSet.insert(x[i]);

        }

 

        int Y = 0, X = 0;

        for (int y : ySet)

                 yHash[y] = Y++;

        for (int x : xSet)

                 xHash[x] = X++;

        //좌표 압축한 결과

        for (int i = 0; i < N; i++)

                 arr[yHash[y[i]]][xHash[x[i]]]++;

        //부분합 전처리

        for (int i = 0; i < Y; i++)

                 for (int j = 0; j < X; j++)

                         pSum[i + 1][j + 1] = pSum[i + 1][j] + pSum[i][j + 1] - pSum[i][j] + arr[i][j];

 

        int result = N;

        //i, j를 기준으로 울타리를 이어나갈 때 사분면에 존재하는 최소 소의 숫자를 구한다

        for(int i=0; i<=X; i++)

                 for (int j = 0; j <= Y; j++)

                 {

                         int temp = max(func(0, 0, i, j), func(i, j, Y, X));

                         temp = max(temp, func(0, j, i, X));

                         temp = max(temp, func(i, 0, Y, j));

 

                         result = min(result, temp);

                 }

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~