18808번: 스티커 붙이기 (BOJ C/C++)

18808번: 스티커 붙이기

사용 언어: C++

 

이번 문제는 내용이 길고 그림이 많다 보니 직접 백준 페이지를 확인하는 것이 좋을 것 같다.

 

풀이

문제를 읽고 든 생각-> 1.돌리는 함수를 어떻게 구현할 것인가.

for(int rot=0; rot<4; rot++) { ~ }

일단 돌리는 함수 구현 이전에 90도 마다 돌려야하므로 for문 안에 노트북에 들어가는지 확인(check)하고 들어가면 거기서 다음 모눈종이로 넘어가고 안되면 rotate()해서 계속 확인하다가 270도까지 안되면 그냥 다음 모눈종이로 넘어가면 된다고 생각했다. rotate함수에서 sticker를 중간에 0으로 초기화하지 않아도 되는 이유는 swap(r,c) 때문이다.

rotate() 함수를 돌리고 나서 sticker 배열은 온전히 돌린 모형만 있는 것은 아니지만 swap(r,c)를 하면 check 함수에서

for(int i=0; i<r; i++)
        for(int j=0; j<c; j++)

우리가 원하는 모눈종이 안의 스티커 모습만 노트북에 붙일 수 있는지 확인하기 때문이다.

2. 노트북에 알맞게 들어가는지 어떻게 구현할 것인가 -> check 함수에 현재 시작할 (x,y) 좌표 인자로 넘겨서 notebook[x+i][y+j]와 sticker[i][j]가 동시에 채워져있으면 겹치는 것이므로 넘긴다. 안 겹치면 sticker의 채워져 있는 부분을 notebook[x+i][y+j]에 채워넣으면 된다.

sticker[k][][]를 쓸까 고민도 했지만 while(k--)로 줄이는 게 편할 것 같아서 줄였다.

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

int n, m, k; //세로, 가로, 스티커 개수
int notebook[42][42];
int sticker[12][12];
int tmp[12][12]; //스티커 돌릴 때 사용할 임시 배열
int r, c; //행, 열의 개수

//노트북에 들어가는지 확인
bool check(int x, int y){
    //노트북이랑 스티커가 겹치면 ret 0;
    for(int i=0; i<r; i++)
        for(int j=0; j<c; j++)
            if(notebook[x+i][y+j] && sticker[i][j]) 
                return 0;
    //하나도 겹치는 부분이 없으면 노트북 공간 채우고 ret 1;
    for(int i=0; i<r; i++)
        for(int j=0; j<c; j++)
            if(sticker[i][j])
                notebook[x+i][y+j] = 1;
    return 1;
}

//돌리기
void rotate(){
    for(int i=0; i<r; i++)
        for(int j=0; j<c; j++)
            tmp[i][j] = sticker[i][j];

    for(int i=0; i<c; i++)
        for(int j=0; j<r; j++)
            sticker[i][j] = tmp[r-j-1][i];
}

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 >> sticker[i][j];

        for(int rot=0; rot<4; rot++){ //0도, 90도, 180도, 270도 순으로 맞아 들어가는지 확인
            bool ischeck = false;
            for(int i=0; i<=n-r; i++){
                if(ischeck) break;
                for(int j=0; j<=m-c; j++){ //i>n-r, j>m-c는 굳이 확인을 안 해도 된다. 
                    if(check(i,j)){
                        ischeck = true;
                        break;
                    }
                }
            }
            if(ischeck) break;
            rotate(); //스티커가 맞지 않으면 돌려보기
            swap(r,c); //한번 돌리고 나면 모눈종이도 바꿔야하므로
        }
    }
    int ans=0;
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            if(notebook[i][j]) ans++;
    cout << ans << '\n';

    return 0;
}