[BOJ] 18808. 스티커 붙이기

 

*단순 시뮬레이션 

*스티커가 회전한 결과를 미리 저장한다. 

sticker[100][4][10][10]

0: 0도 

1: 90도

2: 180도 

3:270도 

 

*스티커가 순서대로가 아니라 조합을 구하는 건 줄 알고 시간초과를 걱정했는데

다행히 순서대로 붙이는 것이다. 

 

스티커를 순서대로 불러오면서 4방향을 모두 본다. 

check() 에서는 지금 범위에 스티커를 붙일 수 있는지 없는지를 확인하고, 붙일 수 있으면 넣는다. 

여러 곳을 붙일 수 있으면 가장 위쪽을 선택하는 것이기 때문에 그리디하게 해결할 수 있다. 

 

*스티커의 높이와 너비는 차지하는 칸과 동일하지 않기 때문에 sizes라는 백터배열에 저장한 후 가져왔다. 

 

*코드가 많이 더럽다. 시뮬레이션 문제이니, 풀이 방법만 참고하시길..

 

?

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 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131

#include <iostream> #include <vector> #include <cstring> using namespace std; int n, m, k; int map[41][41]; int sticker[101][4][11][11]; typedef pair<int, int> pp; typedef pair<int ,pp> ipp; ipp sizes[101];   void print() {      cout << '\n';     for (int i = 0; i < n; i++) {         for (int j = 0; j < m; j++) {             cout << map[i][j] << ' ';         }         cout << '\n';     }      cout << '\n'; } bool check(int sx, int sy, int ex, int ey, int idx, int dir) {     //채워진 곳이 있으면 안됨           for (int i = sx; i < ex; i++) {         for (int j = sy; j < ey; j++) {                           if (sticker[idx][dir][i-sx][j-sy]) {                 if (map[i][j])                     return false;             }         }               }          return true; } //회전한 형태를 미리 저장해놓는다. void rotate(int idx, int dir, int h, int w) {     //시계방향 회전     //2,5     for (int i = 0; i < h; i++)     {         for (int j = 0; j < w; j++)         {             sticker[idx][dir][j][h - i - 1] = sticker[idx][dir - 1][i][j];         }     } } int main() {       ios_base::sync_with_stdio(0);     cin.tie(0);       cin >> n >> m >> k;       for (int i = 0; i < k; i++)     {         int a, b;         cin >> a >> b;         int cnt = 0;         for (int x = 0; x < a; x++)         {             for (int y = 0; y < b; y++)             {                 cin >> sticker[i][0][x][y];                 if (sticker[i][0][x][y]) cnt++;             }         }         sizes[i] = ipp(cnt, pp(a, b));         //rotate 된 값을 저장한다.         for (int j = 1; j < 4; j++)         {             rotate(i, j, a, b);             swap(a, b);                       }     }     //input       //노트북 크기에 맞춰 스티커를 붙인다.     //스티커의 개수는 최대 100개     int ans = 0;       for (int i = 0; i < k; i++)     {         bool flag = false;         for (int j = 0; j < 4; j++)         {             int h = sizes[i].second.first, w = sizes[i].second.second;             if (j % 2 == 1) swap(h, w);             if (n < h || m < w) continue;               for (int x = 0; x <= n-h; x++) {                 for (int y = 0; y <= m-w; y++) {                                           if (check(x, y, x+h, y+w, i, j)) {                         //이 구역에 아직 스티커가 채워지지 않음                         //붙인다.                                                   for (int p = x; p < x+h; p++) {                             for (int q = y; q< y+w; q++) {                                                                   if (sticker[i][j][p-x][q-y] && !map[p][q])                                     map[p][q] = sticker[i][j][p-x][q-y];                             }                                                       }                                                   // print();                         flag = true;                         break;                     }                 }                 if (flag) break;             }             if (flag) {                 break;             }         }     }     for (int i = 0; i < n; i++) {         for(int j = 0; j < m; j++) {             if (map[i][j]) ans++;         }     }     cout << ans << '\n';     return 0; }