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

백준 18808번 '스티커 붙이기' 풀이입니다. 각 스티커를 최대 4번 회전하며 노트북의 왼쪽 위부터 붙일 수 있는 위치를 완전 탐색하는 시뮬레이션 문제입니다. 배열을 90도 회전하는 공식 (r, c) → (c, R-1-r)을 기억해두면 유용합니다. 붙일 수 있으면 즉시 붙이고 다음 스티커로 넘어가는 그리디 구조입니다.

---

📌 문제 정보

• 번호: 18808
• 제목: 스티커 붙이기
• 난이도: Gold 3
• 분류: 구현, 시뮬레이션

---

💡 접근 방식

완전 탐색 기반 시뮬레이션으로 해결했습니다.

1. 각 스티커를 최대 4번 회전하며 시도
2. 현재 방향으로 (0,0)부터 모든 위치 탐색
3. 붙일 수 있으면 즉시 붙이고 다음 스티커로

---

💻 핵심 코드

static int[][] rotate(int[][] sticker) {
    int R = sticker.length;
    int C = sticker[0].length;
    int[][] next = new int[C][R];

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            next[j][R - 1 - i] = sticker[i][j];
        }
    }
    return next;
}

---

⏳ 복잡도 분석

• 시간 복잡도: K × 4 × N × M × 스티커 크기
• 공간 복잡도: O(N × M + 스티커 전체 크기)

---

📄 전체 코드

package B18808;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N, M, K;
    static int[][][] stickers;
    static int[][] notebook;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        stickers = new int[K][][];
        notebook = new int[N][M];
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            stickers[i] = new int[r][c];
            for (int j = 0; j < r; j++) {
                st = new StringTokenizer(br.readLine());
                for (int k = 0; k < c; k++) stickers[i][j][k] = Integer.parseInt(st.nextToken());
            }
        }
        System.out.println(solve());
    }

    static int solve() {
        for (int i = 0; i < K; i++) {
            int[][] cur = stickers[i];
            for (int j = 0; j < 4; j++) {
                boolean attached = false;
                int R = cur.length, C = cur[0].length;
                for (int k = 0; k <= N - R && !attached; k++) {
                    for (int l = 0; l <= M - C && !attached; l++) {
                        if (canAttach(cur, k, l)) { attach(cur, k, l); attached = true; }
                    }
                }
                if (attached) break;
                cur = rotate(cur);
            }
        }
        int cnt = 0;
        for (int[] row : notebook) for (int v : row) if (v == 1) cnt++;
        return cnt;
    }

    static boolean canAttach(int[][] s, int row, int col) {
        for (int i = 0; i < s.length; i++)
            for (int j = 0; j < s[0].length; j++)
                if (s[i][j] == 1 && notebook[row+i][col+j] == 1) return false;
        return true;
    }

    static void attach(int[][] s, int row, int col) {
        for (int i = 0; i < s.length; i++)
            for (int j = 0; j < s[0].length; j++)
                if (s[i][j] == 1) notebook[row+i][col+j] = 1;
    }

    static int[][] rotate(int[][] s) {
        int R = s.length, C = s[0].length;
        int[][] next = new int[C][R];
        for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) next[j][R-1-i] = s[i][j];
        return next;
    }
}