문제

BOJ 18808, 스티커 붙이기

핵심

• 입력의 크기가 작아 구현에 초점을 맞춘다.
• 혜윤이만의 스티커를 붙이는 방법이 있다. 먼저 스티커를 왼쪽 상단부터 오른쪽 하단까지 붙일 수 있는 곳을 찾아 붙인다. 붙일 수 없다면 90도 회전한 후 다시 왼쪽 상단부터 오른쪽 하단까지 찾아봐야 한다.
• 구현 문제답게 실수할 부분이 많다. 일단 스티커를 붙이는 곳을 왼쪽 상단부터 하단까지 탐색 후에 회전해야 한다. 붙일 수 없다고 해서 바로 회전하면 안 된다. 노트북에 스티커가 이미 붙여져 있고(1), 스티커도 1로 채워져 있으면 스티커를 붙일 수 없다고 판단한다. 스티커를 붙일 때도 주의해야 한다. 노트북에 바로 스티커를 붙이게 되면 스티커에서 칠하지 않은 부분(0)이 노트북에 이미 스티커가 붙여진 부분(1)을 덮어쓰게 된다. 즉, 노트북에 빈 곳에만 스티커를 붙인다.
• 스티커를 90도 회전하는 것은 작은 직사각형을 그려놓고, 배열의 요소가 어떻게 이동하는지 보면 규칙을 찾아낼 수 있다. 회전하면 직사각형의 세로는 가로가 되고, 가로는 세로가 된다. 또한 행에 위치한 숫자는 열로 바뀌게 된다. 이를 고려하여 수식을 세우면 다음과 같다.

for (int i = 0; i < r; ++i) {
	for (int j = 0; j < c; ++j)
		temp[j][r - i - 1] = sticker[i][j];
}

• inplace 회전이 아니기에 수식이 간단하지만, 추가적인 메모리(temp)가 필요하다. 스티커를 돌리고 다시 원상 복귀할 필요가 없으므로 3번만 돌리고 다음 스티커로 넘어가는 식으로 구현하였다.

개선

코드

시간복잡도

• $O(k \times 4 \times n \times m \times r \times c)$

C++

#include <iostream>
using namespace std;

int n, m, k;
int note[44][44];
int sticker[14][14];
int r, c;
bool putSticker(int y, int x) {
	// checkSticker
	for (int i = y; i < y + r; ++i) {
		for (int j = x; j < x + c; ++j)
			if (note[i][j] == 1 && sticker[i - y][j - x] == 1)
				return false;
	}
	// putSticker
	for (int i = y; i < y + r; ++i) {
		for (int j = x; j < x + c; ++j) {
			if (note[i][j] == 0)
				note[i][j] = sticker[i - y][j - x];
		}
	}
	return true;
}

void rotate() {
	int temp[14][14] = {};
	for (int i = 0; i < r; ++i) {
		for (int j = 0; j < c; ++j)
			temp[j][r - i - 1] = sticker[i][j];
	}
	swap(r, c);
	for (int i = 0; i < r; ++i) {
		for (int j = 0; j < c; ++j)
			sticker[i][j] = temp[i][j];
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	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];
			}
		}
		bool isAttached = false;
		for (int ro = 0; ro < 4; ++ro) {
			if (ro != 0)
				rotate();
			if (isAttached)
				break;
			for (int i = 0; i <= n - r; ++i) {
				if (isAttached)
					break;
				for (int j = 0; j <= m - c; ++j) {
					if (putSticker(i, j)) {
						isAttached = true;
						break; 
					}
				}
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (note[i][j] == 1)
				++ans;
		}
	}
	cout << ans;
}

Java

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

public class J18808_스티커붙이기 {
    static int n, m, k;
    static int[][] note = new int[44][44];
    static int[][] sticker = new int [14][14];
    static int r, c;
    static void rotate() {
        int[][] temp = new int[14][14];
        for (int i = 0; i < r; ++i) {
            for (int j = 0; j < c; ++j) {
                temp[j][r - i - 1] = sticker[i][j];
            }
        }
        int tmp = r;
        r = c;
        c = tmp;
        for (int i = 0; i < r; i++)
            System.arraycopy(temp[i], 0, sticker[i], 0, c);
    }

    static boolean putSticker(int y, int x) {
    	// checkSticker
        for (int i = y; i < y + r; ++i) {
            for (int j = x; j < x + c; ++j) {
                if (note[i][j] == 1 && sticker[i - y][j - x] == 1) {
                    return false;
                }
            }
        }
        // putSticker
        for (int i = y; i < y + r; ++i) {
            for (int j = x; j < x + c; ++j) {
                if (note[i][j] == 0) {
                    note[i][j] = sticker[i - y][j - x];
                }
            }
        }
        return true;
    }
    
    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());
        while (k-- > 0) {
            st = new StringTokenizer(br.readLine());
            r = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());
            for (int i = 0; i < r; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < c; j++) {
                    sticker[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            boolean isAttached = false;
            for (int ro = 0; ro < 4; ++ro) {
                if (ro != 0)
                    rotate();
                if (isAttached)
                    break;
                for (int i = 0; i <= n - r; i++) {
                    if (isAttached) break;
                    for (int j = 0; j <= m - c; j++) {
                        if (putSticker(i, j)) {
                            isAttached = true;
                            break;
                        }
                    }
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (note[i][j] == 1)
                    ++ans;
            }
        }
        System.out.println(ans);
        br.close();
    }
}