[백준][C++] 18808번: 스티커 붙이기 (264)

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

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

18808번: 스티커 붙이기

 

생각의 흐름

이게 생각보다 쉬운것 같으면서 약간 구현이 빡신 문제이다.

 

애당초 생각을 많이 하기보다는, 문제 그대로 구현만 계속 하면 되는 문제이다.

배열의 크기도 최대 40*40 이라 brute force 방식으로 해결하면 된다 생각하였다.

 

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

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

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

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

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

 

나의 코드

#include <bits/stdc++.h>

using namespace std;

int N, M, K;
int R, C;

int MAP[41][41];
int sticker[41][41];
int cpy_sticker[41][41];

bool isPossibleStick(int x, int y) {
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (MAP[x + i][y + j] == 1 && sticker[i][j] == 1) return false;
        }
    }
    return true;
}

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];
        }
    }
}

void stick(int x, int y) {
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (sticker[i][j] == 1) MAP[x + i][y + j] = 1;
        }
    }
}

void solution() {
    for (int rotation = 0; rotation < 4; rotation++) {
        for (int i = 0; i + R <= N; i++) {
            for (int j = 0; j + C <= M; j++) {
                if (isPossibleStick(i, j)) {
                    stick(i, j);
                    return;
                }
            }
        }
        rotate();
    }
}

int main() {
    ios_base::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];
            }
        }

        solution();

        memset(sticker, 0, sizeof(sticker));
        memset(cpy_sticker, 0, sizeof(cpy_sticker));
    }

    int answer = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (MAP[i][j]) answer++;
        }
    }
    cout << answer << "\n";

    return 0;
}