백준 18808번 [스티커 붙이기](C++) -yes6686- 티스토리

백준 문제 풀이: 18808 [스티커 붙이기]

---

문제 링크: https://www.acmicpc.net/problem/18808

문제 설명:

노트북의 크기와 스티커의 정보를 입력받아, 스티커를 노트북에 붙이는 문제입니다. 스티커를 90도씩 회전하여 최대 4번까지 시도해 붙일 수 있으며, 이미 붙인 영역에 스티커를 겹쳐서 붙일 수는 없습니다. 모든 스티커를 붙인 후, 노트북에 붙여진 스티커 영역의 칸 수를 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <string.h>
using namespace std;

int arr[101][11][11]; // 스티커 원본 배열
int c_arr[101][11][11]; // 회전 후 임시 배열
int n, m, k; // 노트북 크기 (n, m) 및 스티커 수 (k)
int ans[41][41]; // 노트북 상태 저장

void go(int s, int r, int c, int d) {
    if (d == 1) {
        // 원래 스티커 시도
        for (int i = 0; i <= n - r; i++) {
            for (int j = 0; j <= m - c; j++) {
                int check = 1;
                for (int h = i; h < i + r; h++) {
                    for (int b = j; b < j + c; b++) {
                        if (check == 0) break;
                        if (arr[s][h - i][b - j] == 1 && ans[h][b] == 1) {
                            check = 0;
                            break;
                        }
                    }
                }
                if (check == 1) {
                    for (int h = i; h < i + r; h++) {
                        for (int b = j; b < j + c; b++) {
                            if (arr[s][h - i][b - j] == 1) {
                                ans[h][b] = 1;
                            }
                        }
                    }
                    return;
                }
            }
        }
        go(s, c, r, d + 1);
    } else if (d == 2 || d == 3 || d == 4) {
        // 스티커 회전
        memset(c_arr, 0, sizeof(c_arr));
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                c_arr[s][i][j] = arr[s][c - j - 1][i];
            }
        }
        memcpy(arr[s], c_arr[s], sizeof(c_arr[s]));

        for (int i = 0; i <= n - r; i++) {
            for (int j = 0; j <= m - c; j++) {
                int check = 1;
                for (int h = i; h < i + r; h++) {
                    for (int b = j; b < j + c; b++) {
                        if (check == 0) break;
                        if (arr[s][h - i][b - j] == 1 && ans[h][b] == 1) {
                            check = 0;
                            break;
                        }
                    }
                }
                if (check == 1) {
                    for (int h = i; h < i + r; h++) {
                        for (int b = j; b < j + c; b++) {
                            if (arr[s][h - i][b - j] == 1) {
                                ans[h][b] = 1;
                            }
                        }
                    }
                    return;
                }
            }
        }
        if (d == 4) return;
        go(s, c, r, d + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m >> k;
    for (int i = 0; i < k; i++) {
        int r, c;
        cin >> r >> c;
        for (int j = 0; j < r; j++) {
            for (int h = 0; h < c; h++) {
                cin >> arr[i][j][h];
            }
        }
        go(i, r, c, 1);
    }

    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (ans[i][j] == 1) {
                count++;
            }
        }
    }
    cout << count << '\n';

    return 0;
}

예제 입력:

4 4 1
3 3
1 1 1
1 0 0
1 0 0

예제 출력:

5

---

코드 설명

• 핵심 알고리즘: 스티커를 붙이는 순서를 시뮬레이션하며, 필요한 경우 90도씩 회전해 최대 4번 시도합니다.
• 구현 세부사항:
  • go 함수는 스티커를 붙이고 회전하며, 붙일 수 있는지 검증합니다.
  • 스티커가 노트북 영역을 초과하거나 이미 점유된 영역에 붙으려 하면 다음 위치 또는 회전을 시도합니다.
• 시간 복잡도:
  • 최악의 경우 모든 스티커에 대해 4번 회전 시도: O(k ⋅ (n ⋅ m ⋅ r ⋅ c))

---

결과

모든 스티커를 붙인 후 노트북에 붙여진 영역의 칸 수를 출력합니다. 스티커 회전 및 조건 검사를 연습하기에 적합한 문제입니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!