백준 18808 스티커 붙이기

작성일 | In |

Problem : 스티커 붙이기

유형 : 구현, 완전 탐색

문제 , 예제 설명

링크로 대체합니다

해결 전략

정말 시키는대로 충실히 구현을 하면된다.
좌측 상단부터 범위 내까지 스티커를 붙일수 있는지를 확인한다.
불가능하다면 스티커를 돌린다음 위의 작업을 반복한다.

주의할 점

  • 돌리고 난뒤, 가로 세로 길이를 swap 해줘야한다
    • 5 x 3 의 스티커를 90도로 돌리면 3 x 5 가 된다.
  • 스티커의 크기가 노트북에 딱 맞는 경우를 고려해줘야 한다.
    • 노트북이 2 x 2 일때, 스티커의 크기도 2 x 2 라면 스티커를 붙일 수 있다.
    • 즉 {0, 0} 에도 붙일 수 있다. < 가 아닌 <= 처리를 해주어야 한다.

풀이

각 기능별로 쪼개서 함수를 구현했다.

  • 스티커를 노트북에 붙이려고 시도하는 함수
  • 스티커가 노트북에 붙일 수 있는지 확인하는 함수 <= 처리 주의
  • 스티커를 붙이는 함수
  • 스티커를 회전 시키는 함수.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>
using namespace std;

bool board[42][42];
bool sticker[12][12];
int n, m;
int s_n, s_m;
int k;


int get_answer() {
    int ret = 0;
    for (int i = 0; i < n; ++i) {
        for (int ii = 0; ii < m; ++ii) {
            if (board[i][ii]) ret++;
        }
    }
    return ret;
}

void rotate() {
    bool backup_sticker[12][12];
    memcpy(backup_sticker, sticker, sizeof(sticker));

    for (int i = 0; i < s_m; ++i) {
        for (int ii = 0; ii < s_n; ++ii) {
            sticker[i][ii] = backup_sticker[(s_n - 1) - ii][i];
        }
    }
    swap(s_n, s_m);

}

void attach(int i, int ii) {
    for (int x = i; x < i + s_n; ++x) {
        for (int y = ii; y < ii + s_m; ++y) {
            if (sticker[x - i][y - ii]) board[x][y] = true;
        }
    }
}

bool check(int i, int ii) {
    for (int x = i; x < i + s_n; ++x) {
        for (int y = ii; y < ii + s_m; ++y) {
            if (!sticker[x - i][y - ii])continue;
            if (board[x][y]) return false;
        }
    }
    attach(i, ii);
    return true;
}

bool try_attach() {
    for (int i = 0; i <= n - s_n; ++i) {
        for (int ii = 0; ii <= m - s_m; ++ii) {
            if (check(i, ii)) return true;
        }
    }
    return false;
}

void input_sticker() {
    memset(sticker, false, sizeof(sticker));
    cin >> s_n >> s_m;
    for (int i = 0; i < s_n; ++i) {
        for (int ii = 0; ii < s_m; ++ii)
            cin >> sticker[i][ii];
    }
}

void solve() {
    while (k--) {
        input_sticker();
        if (try_attach()) continue;
        for (int i = 0; i < 3; ++i) {
            rotate();
            if (try_attach()) break;
        }
    }
    cout << get_answer();
}

void input() {
    cin >> n >> m >> k;

    solve();
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    input();

    return 0;
}

피드백

rotate 같은 경우 빈출 빈도가 잦다.
함수 구현을 실수 없이 정확하게 해야한다.