[BOJ] 18808. 스티커 붙이기

 

*단순 시뮬레이션 

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

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