2539번: 모자이크

2022.01.23

 

문제 출처:

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

 

문제 분석:

잘못 칠해진 칸들의 좌표들을 정해줬을 때 이를 덮을 수 있는 정사각형 색종이의 가장 작은 크기를 구하는것.

사용할 정사각형의 색종이의 개수는 정해져 있다.

 

문제 해결:

문제에서 주어지는 예시 처럼 3cm 정사각형 색종이 4개로 덮을 수 있다.

그렇다면 4cm 정사각형 색종이 4개로도 덮을 수 있다.

즉, 답보다 큰 색종이들로는 모두 조건을 만족 하고, 정답보다 작은 크기의 색종이를 걸러내는 이분탐색을 사용하면 답에 한없이 가까워 질 수 있는 것이다.

 

이 때, 걸러내는 부분에서는 첫 잘못 칠해진 칸 기준으로 색종이를 점점 늘려갔을때 제한된 색종이 개수보다 많이 들면 false를 return 하는 것으로 답을 구할 수 있다.

 

 

내 소스코드:

#define F first
#define S second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int INF = 987654321;

int row, column;
int limit;
int miss;
vector<pii> arr;

bool cmp(pii a, pii b)
{
   return a.S < b.S;
}

bool check(int size)
{
   int cnt = 1;
   int l = arr[0].S + size - 1;
   for (int i = 1; i < miss; i++)
   {
      if (arr[i].S <= l)
         continue;
      cnt++;
      l = arr[i].S + size - 1;
      if (cnt > limit)
         return false;
   }

   return true;
}

int main()
{
   scanf("%d %d", &row, &column);
   scanf("%d", &limit);
   scanf("%d", &miss);

   arr.resize(miss);

   int maxhi = -1;
   for (int i = 0; i < miss; i++)
   {
      int a, b;
      scanf("%d %d", &a, &b);
      arr[i] = {a, b};
      if (a > maxhi)
         maxhi = a;
   }

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

   int low = maxhi;
   int high = max(row, column);
   int ans = 0;

   while (low <= high)
   {
      int mid = (low + high) / 2;

      if (check(mid))
      {
         ans = mid;
         high = mid - 1;
      }
      else
         low = mid + 1;
   }
   printf("%d", ans);

   return 0;
}

 

고찰: 

이번 문제도 고민해 봤지만 못풀어서 힌트를 얻었다. dp, 구현 쪽이라고 생각했지만 전혀 아니었고 이분탐색이었다.

정해진 조건에 큰 범위에서 정확히 떨어지는 값을 찾는 문제라 이분탐색으로 판단할 수 있는 근거가 있는 것같다.

 

이분탐색으로 푸는 문제인것을 알아도 구현 할때마다 틀리는것 같다;

위의 While문에서도 low < high 라 하면 답이 나오지 않는것 처럼 큰 범위에서 접근 하기 떄문에 디버깅도 쉽지 않아서 어려운것 같다.