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

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

#include <iostream>
#include <vector>

using namespace std;

int n, m, k;
int turn;
int st_l, st_w;

struct sticker {
    int x_len, y_len;
};

void rotateSticker(vector<vector<int>>& stic) {
    int width = stic[0].size();
    int length = stic.size();
    vector<vector<int>> tmp(width, vector<int>(length));

    for (int i = 0; i < length; i++) {
        for (int j = 0; j < width; j++) {
            tmp[j][length-1-i] = stic[i][j];
        }
    }

    stic = tmp;
}

int attachSticker(vector<vector<int>> &nb, vector<vector<int>>& stic) {
    vector<vector<int>>::iterator iter;
    vector<int>::iterator it;
    int nb_l = nb.size(); int nb_w = nb[0].size();
    int stic_l = stic.size(); int stic_w = stic[0].size();

    if (nb_l >= stic_l && nb_w >= stic_w) {
        for (int start_l = 0; start_l <= nb_l - stic_l; start_l++) {
            for (int start_w = 0; start_w <= nb_w - stic_w; start_w++) {
                int tmp = 0;
                for (int i = 0; i < stic_l; i++) { // 현재 상태에서 붙여보기
                    for (int j = 0; j < stic_w; j++) {
                        if (nb[i + start_l][j + start_w] * stic[i][j]) { // 안 붙으면 다음 위치 조사
                            tmp = 1;
                            break;
                        }
                    }
                    if (tmp) {
                        break;
                    }
                }
                if (!(tmp)) { // 붙었으면
                    for (int i = 0; i < stic_l; i++) {
                        for (int j = 0; j < stic_w; j++) {
                            nb[i + start_l][j + start_w] += stic[i][j];
                        }
                    }
                    return 1;
                }
            }
        }
    }
    if (turn--) { // 아직 3번을 안 돌았으면
        rotateSticker(stic);
        if (attachSticker(nb, stic)) { // 돌리고 다시 시도
            return 1;
        }
        else {
            return -1; // 붙일 수 없음
        }
    }
    else { // 붙일 수 없음
        return -1;
    }

    return 1;
}

int remainBlock(vector<vector<int>> obj) {
    int obj_l = obj.size(); int obj_w = obj[0].size();
    int sum = 0;
    for (int i = 0; i < obj_l; i++) {
        for (int j = 0; j < obj_w; j++) {
            if (obj[i][j] != 0) {
                sum++;
            }
        }
    }
    return sum;
}

void printArr(vector<vector<int>> obj) {
    int obj_l = obj.size(); int obj_w = obj[0].size();
    for (int i = 0; i < obj_l; i++) {
        for (int j = 0; j < obj_w; j++) {
            cout << obj[i][j] << " ";
        }
        cout << endl;
    }
}

int main() {
    cin >> n >> m >> k;
    vector<vector<int>> notebook(n, vector<int>(m));
    vector<sticker> stickers(k);

    vector<vector<int>>::iterator iter;
    vector<int>::iterator it;

    for (int i = 0; i < k; i++) { // sticker를 하나씩 받으면서
        cin >> stickers[i].y_len >> stickers[i].x_len;
        int x_len = stickers[i].x_len;
        int y_len = stickers[i].y_len;

        vector<vector<int>> one_sticker(y_len, vector<int>(x_len));
        for (int j = 0; j < stickers[i].y_len; j++) {
            for (int k = 0; k < stickers[i].x_len; k++) {
                cin >> one_sticker[j][k];
            }
        }
        turn = 3;

        attachSticker(notebook, one_sticker);
        printArr(notebook);

    }
    cout << remainBlock(notebook);
}

아직 코드를 보기 좋게, 간결하게 짜는 연습이 덜 된 듯하다. 그리고 구현하는데 소요된 시간이 약 2시간 정도인 것으로 보아 아직 구현이 느리다.

 

 

4중 FOR문을 돌면서 스티커가 부착되는 지 확인하였고, 스티커 부착이 안되는 경우 최대 4번까지 해당 함수를 실행하여야하기 때문에 4*N(노트북 행)*M(노트북 열)*R(스티커 행)*C(스티커 열)의 시간복잡도가 나온다. 또한 이러한 과정을 스티커마다 실행하기 때문에 K번 이 과정을 실행하게 된다.

 

따라서 시간 복잡도는 4KNMRC이므로 주어진 입력의 범위에 따라 최대 1.6*10^(7) 이 되어 시간이 부족할 일은 없다 :> 심지어 이 문제의 시간 제한은 2초이고 메모리도 512MB로 넉넉하게 주어졌다.

 

 

 

깨달은 것

참고 : https://blog.encrypted.gg/938?category=730176

정답 코드를 보고 발전시킬 점을 적어보았다.

 

1. cin, cout, endl 은 생각보다 느리다.

cin, cout보다 scanf, printf를 쓰는 것이 낫고, cin, cout을 쓰려면

ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

이렇게 가속화시킬 수는 있으나 그래도 더 느리다. 또한 sync_with_stdio로 넘겨주는 매개변수 값이 false가 되면 thread unsafe(쓰레드의 순서를 예측할 수 없음)해지기 때문에 예상치 못한 값이 나올 수도 있으므로 쓰지 않는 것이 좋다.

c 표준 입출력함수를 쓰자.

시간을 더 단축시키고 싶다면 글자 하나씩 입출력하는 getchar, putchar 등이 더 빠르다.

참고: https://eine.tistory.com/entry/CC-%EC%9E%85%EC%B6%9C%EB%A0%A5-%EB%B0%A9%EB%B2%95%EC%97%90-%EB%94%B0%EB%A5%B8-%EC%86%8D%EB%8F%84-%EC%A0%95%EB%A6%AC

 

2. 노트북의 크기가 최대 40이고 스티커 크기가 최대 10으로 작다.

굳이 vector 구조체를 안쓰고 int 배열을 max size로 잡아서 사용해도 된다.

 

3. 스티커가 붙은 블록의 갯수 확인

   갯수를 확인할 때 본인은 if문으로 노트북의 해당 칸이 1인지 판단하였으나, 그냥 sum에 모든 노트북 칸의 값을 더해주면 되는 일이었다. 쓸데없이 비교함수를 하나 더 사용하였다.