[백준 18808번] 스티커 붙이기

문제 링크: https://www.acmicpc.net/problem/18808

18808번: 스티커 붙이기

<문제 풀이> 시뮬레이션

이 문제는 배열을 회전하는 것만 잘 구현하면 되는 문제이다.

 

배열을 그려서 규칙을 잘 보면 X행에 있는 모든 원소는 90도 회전하면 Y열로 이동하고,

row, col 값이 서로 바뀐다

 

/*idx 번째 스티커를 1회전*/

void rotate(int idx) {

    int temp[10][10];

    for (int x = 0; x < R[idx]; x++) {

        for (int y = 0; y < C[idx]; y++) {

            temp[x][y] = sticker[idx][x][y];

        }

    }

    swap(R[idx], C[idx]);

    for (int x = 0; x < R[idx]; x++) {

        for (int y = 0; y < C[idx]; y++) {

            sticker[idx][x][y] = temp[C[idx] - 1 - y][x];

        }

    }

}

 

배열 회전만 구현하면 나머지는 문제 조건 그대로 구현하면 끝이다.

 

 

<C++ 소스 코드>

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <cmath>
#include <deque>
#include <cstdlib>
using namespace std;
 
int N, M, K;
 
int sticker[100][10][10];
bool notebook[40][40];
int R[100];
int C[100];
 
 
/*idx 번째 스티커를 1회전*/
void rotate(int idx) {
    int temp[10][10];
    for (int x = 0; x < R[idx]; x++) {
        for (int y = 0; y < C[idx]; y++) {
            temp[x][y] = sticker[idx][x][y];
        }
    }
    swap(R[idx], C[idx]);
    for (int x = 0; x < R[idx]; x++) {
        for (int y = 0; y < C[idx]; y++) {
            sticker[idx][x][y] = temp[C[idx] - 1 - y][x];
        }
    }
}
 
/*idx번째 스티커를 붙여본다 성공 true, 실패 false*/
bool solve(int idx) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            bool flag = true;
            for (int x = 0; x < R[idx]; x++) {
                if (!flag)break;
                for (int y = 0; y <C[idx]; y++) {
                    if (sticker[idx][x][y] == 0)continue;
                    if (i + x >= N || j + y >= M) { // 범위를 벗어나면 실패
                        flag = false;
                        break;
                    }
                    if (notebook[i + x][j + y]) { //이미 스티커가 붙어있으면 실패
                        flag = false;
                        break;
                    }
                }
            }
            if (flag) { // 스티커를 붙일 수 있으면
                for (int x = 0; x < R[idx]; x++) {
                    for (int y = 0; y < C[idx]; y++) {
                        if (sticker[idx][x][y] == 0)continue;
                        notebook[i + x][j + y] = true;
                    }
                }
                return true;
            }
 
        }
 
    }
    return false;
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> N >> M >> K;
 
    for (int i = 0; i < K; i++) {
        cin >> R[i] >>C[i];
        for (int x = 0; x < R[i]; x++) {
            for (int y = 0; y < C[i]; y++) {
                cin >> sticker[i][x][y];
            }
        }
    }
    
    for (int i = 0; i < K; i++) {
        for (int rotate_cnt = 0; rotate_cnt < 4; rotate_cnt++) {
            if(solve(i)) break;
            rotate(i);
        }
    }
    int cnt = 0;
    for (int i = 0; i < N; i++) {
        for (int j =0; j < M; j++) {
            if (notebook[i][j])cnt++;
        }
    }
    cout << cnt;
 
    return 0;
}