[Codeground 30번] Rectangles

문제 출처 :

https://www.codeground.org/practice/practiceProblemList

알고리즘 분석 :

문제 해결에 필요한 사항

1. sort

이 문제는 사각형이 그 사각형을 포함하고, 또 다른 사각형이 다른 사각형을 포함하고 ... 이러한 가장 많이 중첩된 사각형의 개수를 구하는 문제이다.

우선 이렇게 문제를 구성하기 위해 sort를 하게되는데 sort의 기준을 가장 큰 사각형부터 나타나도록 지정한다.

그러한 compare의 기준은 아래 comp의 내용을 통해 확인한다.

그 뒤에 이중 포문을 통해 문제를 해결하면 시간 복잡도는 O(k^2)에 해결 할 수 있다.

이중포문에서 하나의 제약으로는 두 사각형이 같은 경우에는 depth를 갱신해주지 않는다는 것이다.

이때 k가 5000이기에 25,000,000으로 충분히 시간 내에 통과 할 수 있는 범위이다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89

#include <iostream> #include <cstdio> #include <algorithm> #include <memory.h>   using namespace std;   typedef struct _REC_ {     int x1, y1;     int x2, y2; }REC;   REC rec[6000]; int ans; int depth[6002];   bool comp(const REC &a, const REC &b) {     // a b 사각형의 x1, y1이 모두 같다면     if (a.x1 == b.x1  && a.y1 == b.y1)     {         // a b 사각형의 x2가 같다면 y2로 정렬         if (a.x2 == b.x2)             return a.y2 > b.y2;           // x2로 정렬         return a.x2 > b.x2;     }       // a b 사각형의 x1만 같다면 y1으로 정렬     if (a.x1 == b.x1)         return a.y1 < b.y1;       // x1으로 정렬     return a.x1 < b.x1; }   int main() {     int tcase;     scanf("%d", &tcase);       for (int tc = 1; tc <= tcase; tc++)     {         int n, m, k;         scanf("%d %d %d", &n, &m, &k);           memset(rec, 0, sizeof(rec));         memset(depth, 0, sizeof(depth));           ans = 0;           for (int i = 0; i < k; i++)             scanf("%d %d %d %d", &rec[i].x1, &rec[i].y1, &rec[i].x2, &rec[i].y2);           sort(rec, rec + k, comp);           // 사각형 하나씩         for (int i = 0; i < k; i++)         {             for (int j = 0; j < k; j++)             {                 // j 사각형이 i 사각형에 포함될 때                 if (rec[i].x1 <= rec[j].x1 && rec[i].y1 <= rec[j].y1 && rec[i].x2 >= rec[j].x2 && rec[i].y2 >= rec[j].y2)                 {                     // i, j 사각형이 완전 같지 않을때                     if (!(rec[i].x1 == rec[j].x1 && rec[i].y1 == rec[j].y1 && rec[i].x2 == rec[j].x2 && rec[i].y2 == rec[j].y2))                     {                         // j의 depth를 갱신                         if(depth[j] < depth[i] + 1)                             depth[j] = depth[i] + 1;                     }                       // ans 갱신                     ans = max(ans, depth[j]);                 }             }         }           // 자신을 포함해야 하니 +1         printf("Case #%d\n%d\n", tc, ans + 1);     }       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus