[Algorithm]Baekjoon 2539번 :: 모자이크

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

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
#include <thread>
#include <atomic>
 
using namespace std;
  
struct Node
{
    int y;
    int x;
};
 
bool cmp(const Node& a, const Node& b)
{
    return a.x < b.x;
}
 
int n, m, paperCount, wrongCount, wy, wx;
int minSize = 0;
vector<Node> wrongNodes;
 
bool check(int paperSize) 
{
    int tempPaperCount = 1;
    int rangeSizeX = wrongNodes[0].x + paperSize - 1;
 
    for (int i = 1; i < wrongNodes.size(); ++i)
    {
        int x = wrongNodes[i].x;
 
        if (x > rangeSizeX) // 이전에 붙였던 색종이를 벗어나면
        {
            // 새로 붙인다.
            ++tempPaperCount;
            rangeSizeX = x + paperSize - 1;
 
            if (rangeSizeX >= m) // 끝까지 했으면
            {
                break;
            }
        }
    }
 
    return tempPaperCount <= paperCount;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m >> paperCount >> wrongCount;
 
    for (int i = 0; i < wrongCount; ++i)
    {
        cin >> wy >> wx;
 
        wrongNodes.push_back({ wy,wx });
        minSize = max(minSize, wy);
    }
 
    sort(wrongNodes.begin(), wrongNodes.end(), cmp);
 
    int left = minSize;
    int right = 10000001;
    int answer = 0;
 
    while (left <= right)
    {
        int mid = (left + right) / 2;
 
        if (check(mid))
        {
            right = mid - 1;
            answer = mid;
        }
        else
        {
            left = mid + 1;
        }
    }
 
    cout << answer;
}
 
 

 

 

일정개수 이하의 색종이를 붙여서 잘못 색칠된 곳을 덮으려 할 때, 최소의 색종이 크기를 구하는 문제이다.

이 문제에서 놓치면 안될 중요한 점은 색종이는 반드시 도화지의 밑변에 딱 붙여야 한다는 것이다.

그렇기 때문에 색종이의 최소크기는 잘못 색칠된 칸들 중 y값이 가장 높은 값이다.

 

밑변에 딱 붙여야하기 때문에, 어쩔 수 없이 가장 큰 y값이 최소값 (left)가 될 수 밖에 없다.

이후 문제에서 요구하는 답인 색종이크기값으로 이분탐색을 진행할 건데, 색종이크기는 정해놨으니 정해진 개수이하로 모든 잘못색칠된 칸을 덮을 수 있는지 검사해야 한다.

 

처음에 left값을 최대y값으로 미리 했으니, 검사할 때 y값을 체크할 필욘 없다. 어차피 check할 때의 mid값은 반드시 잘못색칠된 칸의 y값보다 크거나 같으니까.

 

그러니 x값만 체크하면 되는데, rangeSizeX라는 변수를 선언해서 유효한 X범위를 미리 체크해둔다.

잘못색칠된칸들을 순회할 때, 이 칸의 X값이 유효한X범위안이면 이전에 붙인 색종이로 덮여져 있으니 그냥 지나치면 되고, X범위를 넘어서면 새로 붙여야하니 카운팅한다음 rangeSizeX값도 새로 갱신해준다.