[18808 번] 스티커 붙이기

https://www.acmicpc.net/problem/18808

18808번: 스티커 붙이기

문제 자체가 길어서 조금 읽는데 힘들었지만, 문제에서 말하고자하는 내용은 정확하게 파악할 수 있었습니다.

첫번 째로는 노트북에 스티커를 특정 영역에서 붙일 수 있는지 없는지 확인하는 것이 먼저이고, 그 다음에는 스티커를 회전하는 방법이 있습니다.

 

우선 노트북의 (x,y)에 모눈종이의 (0, 0)이 올라가게 스티커를 붙이려면 노트북 위의 스티커가 붙은 칸과 모눈종이 위에 스티커가 붙은 칸이 겹지면 안됩니다. 모눈종이가 올라가는 모든 칸에 대해 노트북과 모눈종이의 스티커가 겹치는 칸이 있는지를 확인하고, 겹치는 칸이 없어 붙일 수 있다면 나타내는 변수의 값을 갱신하면 끝입니다.

bool pastable(int x, int y){
    for(int i=0; i<r, i++){
        for(int j = 0 ; j<c ; j++){
            if(note[x+i][y+j] == 1 && papaer[i][j] == 1)
                return false;
        }
    }
    for(int i=0 ; i<r; i++){
        for(int j=0; j<c; j++){
            if(paper[i][j] == 1)
                note[x+i][y+j] = 1;
        }
    }
    return true;
}

원래 클린코드로 보자면 특정 영역에 붙일 수 있는지 확인하는 함수와 실제 붙이는 파트가 서로 다른 함수로 나뉘는게 좋지만 문제에서의 상황을 그대로 코드로 구현하고자 만들었습니다.

 

 

다음으로는 스티커를 회전하는게 문제입니다. 기존 좌표가 있는데 이를 90도 회전을 시키다보면 회전하고나서의 좌표를 어떤 식으로 갱신해야하는지 규칙을 찾아야하기 때문에 하나하나 원본 좌표와 회전좌표를 비교하자면, 90도를 돌리고 나서는 앞선 원본 행렬의 열 번호는 회전 행렬의 행 번호로 되며, 회전 행렬의 행 번호는 (처음 배열에서 행의 크기) - 1 - (처음 배열의 열 번호) 입니다. 따라서 원본 행렬을 A, 회전 행렬을 B로 하자면 B[x][y] = A[r-1-y][x] 입니다.

void rotate(){
    int tmp[12][12];
    
    for(int i = 0; i<r; i++){
        for(int j= 0 ; j<c; j++)
            tmp[i][j] = paper[i][j];
    }
    for(int i=0; i<c ; i++){
        for(int j=0;j<r;j++)
            paper[i][j] = tmp[r-1-j][i];
    }
    swap(r,c);
}

마지막으로 main문을 짤 때 스티커의 개수만큼 반복문을 전체적으로 실행을 해야하면서 그 안에서 스티커를 임의의 장소를 붙일 수 없을 때 회전하는 경우 (총 4번)을 구현하는 조건을 생각해주어야 합니다. 또한 is_paste라는 boolean변수를 통해서 스티커를 붙일 수 있는지 없는지 확인하는 용도의 변수로 사용을 하며, pastable 함수로 확인되면 is_paste를 true로 변환해줍니다. (default 값은 false) 반복문 내에서 is_paste가 1이 나오지 않는다면 rotate를 마지막에 진행시키고 반복하면 됩니다.

위와 같은 두 함수를 이용해서 전체적인 코드는 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;

int n,m,k;
int note[42][42];
int r,c;
int paper[12][12];

bool pastable(int x, int y){
    for(int i=0; i<r; i++){
        for(int j = 0 ; j<c ; j++){
            if(note[x+i][y+j] == 1 && paper[i][j] == 1)
                return false;
        }
    }
    for(int i=0 ; i<r; i++){
        for(int j=0; j<c; j++){
            if(paper[i][j] == 1)
                note[x+i][y+j] = 1;
        }
    }
    return true;
}

void rotate(){
    int tmp[12][12];
    
    for(int i = 0; i<r; i++){
        for(int j= 0 ; j<c; j++)
            tmp[i][j] = paper[i][j];
    }
    for(int i=0; i<c ; i++){
        for(int j=0;j<r;j++)
            paper[i][j] = tmp[r-1-j][i];
    }
    swap(r,c);
}


int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k;
    while(k--){
        cin >> r >> c;
        for(int i = 0; i<r; i++){
            for(int j = 0; j<c; j++)
                cin >> paper[i][j];
        }
        //스티커를 임의의 장소에 먼저 붙일 수 있는지를 확인
        for(int rot = 0 ;rot <4 ; rot++){
            bool is_paste = false; //스티커를 붙이는데 성공하면 반복문 탈출 용도
            for(int x=0; x<=n-r; x++){
                if(is_paste) break;
                for(int y=0 ; y <= m-c; y++){
                if(pastable(x,y)){
                    is_paste = true;
                    break;
                    }
                }
            }
            if(is_paste) break;
            rotate();
        }
    }
    int cnt=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++)
            cnt += note[i][j];
    }
    cout << cnt << '\n';
    
    return 0;
}