[BOJ] 18808. 스티커 붙이기

BOJ/C++

[BOJ] 18808. 스티커 붙이기

IamToday 2020. 3. 25. 15:00

*단순 시뮬레이션

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

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

0: 0도

1: 90도

2: 180도

3:270도

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

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

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

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

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

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

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

#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;
}