문제

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

1. 스티커를 회전시키지 않고 모눈종이에서 떼어낸다.
2. 다른 스티커와 겹치거나 노트북을 벗어나지 않으면서 스티커를 붙일 수 있는 위치를 찾는다. 혜윤이는 노트북의 위쪽부터 스티커를 채워 나가려고 해서, 스티커를 붙일 수 있는 위치가 여러 곳 있다면 가장 위쪽의 위치를 선택한다. 가장 위쪽에 해당하는 위치도 여러 곳이 있다면 그중에서 가장 왼쪽의 위치를 선택한다.
3. 선택한 위치에 스티커를 붙인다. 만약 스티커를 붙일 수 있는 위치가 전혀 없어서 스티커를 붙이지 못했다면, 스티커를 시계 방향으로 90도 회전한 뒤 2번 과정을 반복한다.
4. 위의 과정을 네 번 반복해서 스티커를 0도, 90도, 180도, 270도 회전시켜 봤음에도 스티커를 붙이지 못했다면 해당 스티커를 붙이지 않고 버린다.

---

풀이

2차원 배열 자체를 회전시키는 방법을 아는 것이 중요하다. (참고: https://taaewoo.tistory.com/10)

예를 들어, 아래와 같은 5 x 5 배열을 시계 방향으로 90도 회전시킨다고 가정하자. (N = 5)

그러면 2차원 배열의 행, 열 인덱스는 다음과 같이 변할 것이다. (배열 전체를 다 보지 않고, 하나의 행과 열의 인덱스만 봐도 규칙성을 발견할 수 있다.)

원본 배열을 A, 회전시킨 배열을 B라고 할 때, A의 1열은 B의 1행이 된다는 걸 알 수 있다.

그렇다면, A의 행과 B의 열 사이의 관계는 어떻게 될까? 가만히 살펴보면... A의 행 번호가 감소할수록 B의 열 번호는 증가한다는 걸 알 수 있다. 그리고 그 둘의 합은 N - 1 = 4이다.

즉, 다음과 같이 일반화 할 수 있다.

B[ B Row ][ B Column ] = A[ N - 1 - B Column ][ B Row ]

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
typedef pair<int, int> pii;

const int MAX = 41; 
int N, M, K; 
int R, C; 

int graph[MAX][MAX];
int sticker[MAX][MAX]; 
int temp[MAX][MAX];

bool isPossibleStick(int x, int y){
	for(int i = 0; i < R; i++){
		for(int j = 0; j < C; j++){
			if(graph[x + i][y + j] == 1 && sticker[i][j] == 1)
				return false; 
		}
	}
	
	return true; 
}

void putSticker(int x, int y){
	for(int i = 0; i < R; i++){
		for(int j = 0; j < C; j++){
			if(sticker[i][j] == 1) graph[x + i][y + j] = 1; 
		}
	}
}

void rotateSticker(){
	// 2차원 배열을 시계방향으로 90도 회전시킨다. 
	for(int i = 0; i < R; i++){
		for(int j = 0; j < C; j++){
			temp[j][R - 1 - i] = 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];  
		}
	}
}

void solution() {
	for(int dir = 0; dir < 4; dir++){
		for(int i = 0; i + R <= N; i++){
			for(int j = 0; j + C <= M; j++){
				if(isPossibleStick(i, j)){
					putSticker(i, j);
					return; 
				}
			}
		}
		
		rotateSticker(); 
	}
}

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

	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]; 
			}
		}

		// i번째 스티커를 붙여본다. (안 되면 시계방향으로 90도 회전)
		solution(); 

		memset(sticker, 0, sizeof(sticker));
		memset(temp, 0, sizeof(temp));
	}

	int blank = 0;
	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			if(graph[i][j] == 0) blank++;
		}
	}
	
	cout << N * M - blank; 

	return 0; 
}