[백준][C++] 18808 스티커 붙이기

www.acmicpc.net/problem/18808

18808번: 스티커 붙이기

 

 

 

알고리즘 종류

    - 구현

 

 

 

사고 과정

    1. 스티커를 순서대로 받아서 sticker 배열에 저장한다.

    2. for문 2개로 노트북 크기인 mat 배열을 돌면서 스티커를 붙일 수 있는지 확인한다.

        2-1. 확인 방법은 mat위치와 sticker의 위치를 비교하는 것이다.

    3. 붙일 수 있으면 붙인다. sticker 배열을 그대로 노트북 mat 배열에 그대로 옮기면 된다.

    4. 붙일 수 없으면 회전시킨다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <cstring>
 
using namespace std;
 
int n, m, k;
int r, c;
int mat[41][41];
int sticker[11][11];
int cpy_sticker[11][11];
 
 
void rotate(){
    
    for(int i=0; i<r; i++){
        for(int j=0; j<c; j++){
            cpy_sticker[j][r-1-i] = sticker[i][j];
        }
    }
    
    int tmp = c;
    c=r;
    r=tmp;
    
    for(int i=0; i<r; i++){
        for(int j=0; j<c; j++){
            sticker[i][j] = cpy_sticker[i][j];
        }
    }
}
 
 
bool isValid(int y, int x){
    return (x>=0 && x<m) && (y>=0 && y<n);
}
 
 
bool isAvail(int i, int j){
    for(int y=0; y<r; y++){
        for(int x=0; x<c; x++){
            if(mat[i+y][j+x] && sticker[y][x]) return false;
            //if(!isValid(i+y, j+x)) return false;
        }
    }
    return true;
}
 
 
void stick_to(int i, int j){
 
    for(int y=0; y<r; y++){
        for(int x=0; x<c; x++){
            if(sticker[y][x]==1)
                mat[i+y][j+x] = 1;
        }
    }
}
 
void solution(){
    
    for(int ro=0; ro<4; ro++){
        for(int i=0; i<=n-r; i++){
            for(int j=0; j<=m-c; j++){
                if(isAvail(i, j)){
                    stick_to(i, j);
                    return;
                }
            }
        }
        rotate();
    }
}
 
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.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];
            }
        }
        solution();
    }
    
    int answer = 0;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(mat[i][j]) answer++;
        }
    }
    cout << answer << endl;
 
}

 

    - 정리하기 전 코드

 

#include <iostream>
#include <vector>
#include <cstring>
 
using namespace std;
 
int n, m, k;
int mat[41][41];
int stickers[101][11][11];
int cpy_stickers[101][11][11];
vector<pair<int, int> > sticker_info;
 
void rotate(int no){
    
    int r = sticker_info[no].first;
    int c = sticker_info[no].second;
    
    for(int i=0; i<r; i++){
        for(int j=0; j<c; j++){
            cpy_stickers[no][j][r-1-i] = stickers[no][i][j];
        }
    }
    
    sticker_info[no].first = c;
    sticker_info[no].second = r;
    
    for(int i=0; i<c; i++){
        for(int j=0; j<r; j++){
            stickers[no][i][j] = cpy_stickers[no][i][j];
        }
    }
}
 
bool isValid(int y, int x){
    return (x>=0 && x<m) && (y>=0 && y<n);
}
 
bool isAvail(int i, int j, int no){
    int r = sticker_info[no].first;
    int c = sticker_info[no].second;
    
    for(int y=0; y<r; y++){
        for(int x=0; x<c; x++){
            if(mat[i+y][j+x]==1 && stickers[no][y][x]==1) return false;
            //if(!isValid(i+y, j+x)) return false;
        }
    }
    return true;
}
 
void stick_to(int i, int j, int no){
    int r = sticker_info[no].first;
    int c = sticker_info[no].second;
    
    for(int y=0; y<r; y++){
        for(int x=0; x<c; x++){
            if(stickers[no][y][x]==1)
                mat[i+y][j+x] = 1;
        }
    }
}
 
void stick(int no){
    
    for(int ro=0; ro<4; ro++){
        
        int r = sticker_info[no].first;
        int c = sticker_info[no].second;
    
        for(int i=0; i<=n-r; i++){
            for(int j=0; j<=m-c; j++){
                if(isAvail(i, j, no)){
                    stick_to(i, j, no);
                    return;
                }
            }
        }
        
        rotate(no);
    }
    
}
 
 
void solution(){
    for(int i=0; i<k; i++){
        stick(i);
    }
    
    int answer = 0;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(mat[i][j]) answer++;
        }
    }
    cout << answer << endl;
}
 
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> n >> m >> k;
    
    for(int a=0; a<k; a++){
        int r, c;
        cin >> r >> c;
        sticker_info.push_back({r, c});
        
        for(int i=0; i<r; i++){
            for(int j=0; j<c; j++){
                cin >> stickers[a][i][j];
            }
        }
    }
    
    solution();
}

 

 

시행착오

    - 생각보다 쉬운 문제였다. 테스트케이스 모두 통과하는데 1시간 정도 걸렸다. 그러나 제출이 안되서 디버깅 한다고 1시간을 넘게 추가로 사용했다. 원인은 아래 코드이다. 스티커를 붙일 수 없으면 회전시켜야 한다. 본인도 회전시켰다. 회전을 이상하게 했다. 아래 코드는 마치 경우에 따라 회전을 달리하는 코드와 같다. for문이 끝날 때에 rotate()을 한 번 해주면 되는데... 본인은 무슨 생각이었을까... 여튼, 이거 찾느라 머리가 지끈했다. 

void solution(){
    for(int ro=0; ro<4; ro++){
        if(ro==1) rotate();
        else if(ro==2) {
            rotate();
            rotate();
        }
        else if(ro==3){
            rotate();
            rotate();
            rotate();
        }
    
        for(int i=0; i<=n-r; i++){
            for(int j=0; j<=m-c; j++){
                if(isAvail(i, j)){
                    stick_to(i, j);
                    return;
                }
            }
        }
    }
 
}

 

    - 위와 같은 사태를 다시 반복하지 않기 위한 솔루션은 글에서 제시한 대로 구현하면 된다. 문제에서 회전되지 않은 스티커를 붙일 공간을 찾아보고 찾지 못하면 --> 회전시키라고 했다. 즉, rotate()을 for문이 끝나는 시점에 해주면 된다. 문제에서 의도한 대로 구현하면 되겠다.