[백준 2539] 모자이크

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

2539번: 모자이크

 

문제 입력 조건에서 행과 열의 개수가 100만이라 2차원 배열을 사용하면 메모리초과가 난다. 

또한 가장 작은 색종이의 크기를 구하는 문제인데 각 색종이의 크기마다 도화지에 대해 반복문을 돌리면 시간초과가 난다.

따라서 도화지 전체에 대해서가 아니라 잘못 칠해진 페인트에 대해서 반복문을 돌리고,

색종이의 크기에 대해서 이분탐색을 수행하여 색종이의 최소 크기를 구하였다.

 

잘못 칠해진 페인트의 좌표를 pair로 입력받고 x값에 대해 정렬하여 x값이 작은 페인트부터 오름차순으로 탐색하도록 했으며, 문제 조건 중 '모든 색종이는 반드시 도화지의 밑변에 맞추어 붙인다.'라는 조건이 있기 때문에 색종이는 최소한 잘못 칠해진 칸들 중 가장 높이 칠해진 칸의 높이 값보다 커야 한다. 따라서 이를 maxH로 저장해 놓고 이분 탐색의 범위 최솟값으로 지정하였다.

 

 

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

bool cmp(pair<int,int> p1, pair<int,int> p2){
    return p1.second<p2.second;
}

int main(){
    int r,c,paperCnt;
    int maxH=0;
    int wrongPaintCnt;
    vector<pair<int, int>> wrongPaint;
    cin>>r>>c;
    cin >> paperCnt;
    cin >> wrongPaintCnt;

    for (int i = 0; i < wrongPaintCnt; i++) {
        int a,b;
        cin>>a>>b;
        maxH = max(maxH, a);
        wrongPaint.push_back({a, b});
    }

    sort(wrongPaint.begin(),wrongPaint.end(),cmp);

    int left=maxH, right=1000001;
    int mid,ans=right;

    while(left<=right){
        mid=(left+right)/2;
        int paperCntTmp=1;
        int columnTmp=wrongPaint[0].second;

        for (int i = 1; i < wrongPaintCnt; i++) {
            if (wrongPaint[i].second >= columnTmp + mid) {
                paperCntTmp++;
                columnTmp = wrongPaint[i].second;
            }
        }

        if(paperCntTmp <= paperCnt){
            ans=mid;
            right=mid-1;
        }else{
            left = mid + 1;
        }
    }
    cout<<ans;
}