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

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

18808번: 스티커 붙이기

 

나머지 예제 생략

 

문제 이해

정말 그냥 스티커를 붙이는 모든 경우를 생각하면 되는 문제였다.

붙여보고 안되면 다르게 붙여보고 이런식으로...

 

3단계이다.

1. 스티커를 붙여본다.

2. 그 모양으로 못붙이면 돌린다.

3. 4번 돌려봤는데 다 안됐으면 그 스티커는 버린다

 

Try_Stick()

모든 맵 칸에 대해서 그 칸이 스티커의 좌상칸이라고 생각하고, 그 칸에 붙여본다.

만약 붙이는데 맵에 이미 채워진 칸이 있다면 거기엔 못붙인다.

 

사실 처음에 여기서 map[i][j] == 0 이면 continue 하게 했는데, 생각해보니까 스티커 좌상칸이 0이면 map[i][j]가 0이어도 되니까 이 예외처리를 하면 안된다!

Stick()은 여기서 스티커를 (i, j)부터 붙여보는 함수이다. 첫 번째 루프에서는 스티커가 들어가는지 확인하고, 들어가면 두 번째 루프로 가서 실제 맵에 채워넣는다. 

 

Turn_Stick()

그냥 배열에서 많이 다루는 90도 오른쪽으로 돌리기를 하면 된다

 

작성 코드

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
#define MAXNM 40
#define MAXK 100
#define MAXRC 10

int N, M, K;
int R, C;
int map[MAXNM + 5][MAXNM + 5]; // 노트북
int sticker[MAXRC + 1][MAXRC + 1]; // 스티커
int tmp[MAXRC + 1][MAXRC + 1]; // 스티커 돌릴 때 사용할 임시 배열

void Print_Map(void) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cout << map[i][j] << " ";
        }
        cout << "\n";
    }
    cout << "\n";
}

void Print_Sticker(void) {
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cout << sticker[i][j] << " ";
        }
        cout << "\n";
    }
    cout << "\n";
}

int Stick(int r, int c) {
    // 이 위치에 붙여보고 안되면 0 리턴
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if(sticker[i][j] == 1){
                if (map[r + i][c + j] != 0) return 0;
            }
        }
    }

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (sticker[i][j] == 0) continue;
            map[r + i][c + j] = sticker[i][j];
        }
    }
    //cout << "Sticker sticked!\n";
    //Print_Map();
    return 1;
}

int Try_Stick(void) {
    if (R > N || C > M) return 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            //if (map[i][j] == 0) {
                // 여기에 붙일 수 있을 거 같음
                if (i + R > N || j + C > M) continue;
                if (Stick(i, j)) return 1;
            //}
        }
    }
    return 0;
}

void Turn_Sticker(void) {
    memset(tmp, 0, sizeof(tmp));
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            tmp[j][R - 1 - i] = sticker[i][j];
        }
    }
    memset(sticker, 0, sizeof(sticker));
    memcpy(sticker, tmp, sizeof(tmp));
    int tmpRC = R;
    R = C, C = tmpRC;

    //cout << "Turned Sticker: \n";
    //Print_Sticker();
}

int Get_Answer(void) {
    int cnt = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j] == 1) cnt++;
        }
    }
    return cnt;
}
int main(void) {
    freopen("in.txt", "r", stdin);
    cin >> N >> M >> K;
    for (int k = 0; k < K; k++) {
        // 각 스티커 붙이기
        memset(sticker, 0, sizeof(sticker));
        cin >> R >> C;
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                cin >> sticker[i][j];
            }
        }

        //cout << "Current Sticker: \n";
        //Print_Sticker();

        for (int i = 0; i < 4; i++) {
            if (Try_Stick()) break;
            if (i == 3) break;
            //cout << "Failed to stick\n";
            Turn_Sticker();
        }
    }
    //cout << "Final:\n";
    //Print_Map();
    cout << Get_Answer();
    return 0;
}