백준 21277 짠돌이 호석 풀이

힌트 1

입력 제한이 아주 작습니다!

 

힌트 2

둘 중 더 큰 퍼즐 A를 고정시켰다고 가정할 때, 답이 될 수 있는 퍼즐 B의 위치가 얼마나 있는지 잘 생각해보세요.

 

풀이

편의상 두 퍼즐을 A, B라 하겠습니다.

만약 어떤 퍼즐 A를 고정시켜두었다면, 답이 될 수 있는 퍼즐 B의 위치는 다음과 같습니다.

직접 작업을 하다보니 그림 상태는 양해 부탁드립니다 😅

그림을 통해 말하고 싶은 점은, B의 위치가 될 수 있는 가짓수가 얼마 없다는 점입니다. B의 위치가 A 넓이를 벗어나게 되면, 전체 정답은 A에 붙어있느니만 못하기 때문에, 딱 위 그림 영역 정도가 답이 되겠죠.

따라서 저 영역의 범위를 수식으로 계산해봅시다.

문제처럼 A의 행, 열이 (n1, m1) B의 행, 열이 (n2, m2)라고 정하고, A의 왼쪽 위 꼭짓점의 위치를 (0,0)이라 하면 정답이 될 수 있는 B의 왼쪽 위 구석의 위치는 (-n2, -m2)부터 시작하여, 오른쪽 아래 구석의 (n1, m1)까지 쭉 살펴보면 됩니다. (여기서 B의 위치 또한 왼쪽 위 꼭짓점의 위치를 의미합니다.)

따라서 각 퍼즐의 최대 행, 열의 길이는 50이므로 A를 고정했다고 할 때 가능한 B 위치의 가짓수는 최대 100 * 100 = 1만개입니다.  다만 퍼즐은 회전이 가능한데, A, B를 동시에 90도 회전시키면 어차피 같기 때문에 A는 고정시킨 채 퍼즐 B만 회전시켜주면 됩니다. 이때 가짓수를 4배 곱해야 합니다. 따라서 여기까지 4만 가지 경우입니다.

이제 퍼즐 B를 위치시켰다면, A와 겹치는 지 여부를 확인해봐야 합니다. 이 경우 퍼즐 A 또는 B 아무거나 하나 잡고, 해당 퍼즐이 위치한 곳에 B도 있다면 불가능한 경우로 체크하고, 그게 아니라면 정답이 될 수 있으므로 넓이를 계산해 줍니다. 겹치는 걸 확인하는 과정에서 최대 50 * 50 = 2,500 가지입니다. 따라서 여기까지 4만 * 2,500 = 1억 가지 경우입니다.

마지막으로 넓이 계산은 A, B의 영역들 중 (가장 큰 y값 - 가장 작은 y값) * (가장 큰 x위치 - 가장 작은 x위치) 로 계산하면 되며 이 부분은 문제에서 두 퍼즐 모두 4개 모서리에 최소 하나의 1은 존재하는 것이 보장된다. 라는 조건이 있기 때문에 A는 고정되어있으므로 구할 필요 없고, B는 시작 위치와 행, 열의 길이를 토대로 수식 하나로 계산 가능합니다. 따라서 O(1) 시간 복잡도입니다.

최종적으로 1억 번 연산하므로 문제의 제한 시간 2초 이내에 해결 가능합니다. 물론 겹치는 걸 확인하는 과정을 "퍼즐이 존재하는 곳만"을 따로 빼서, 그것만 계산해주면 시간이 단축될 수 있고, B의 위치도 이전 위치를 토대로 다음 위치는 패스하는 등 여러 시간 커팅이 가능하긴 하지만, 코딩 테스트 수준에서 이 부분까지 출제될 가능성이 정말 적으므로 이 정도만 하겠습니다!

 

소스 코드(.cpp)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int arr[151][151]; //전체 액자 크기
int arr1[51][51]; //퍼즐 1
int arr2[51][51]; //퍼즐 2

int n1, n2, m1, m2;

int ans = 999999;

void rotate() {
	int tmp[51][51] = { 0, };
	for (int i = m1 - 1; i >= 0; i--) {
		for (int j = 0; j < n1; j++) {
			tmp[m1 - 1 - i][j] = arr1[j][i];
		}
	}

	for (int i = 0; i <= 50; i++) {
		for (int j = 0; j <= 50; j++) {
			arr1[i][j] = tmp[i][j];
			//cout << arr1[i][j];
		}
		//cout << "\n";
	}
	swap(n1, m1);
}

void go(int y, int x) {
	bool flag = true; //만약 겹치는 숫자가 있다면 false
	for (int i = y; i < y + n1; i++) {
		for (int j = x; j < x + m1; j++) {
			if (arr[i][j] == 1 && arr1[i - y][j - x] == 1) {
				flag = false;
				break;
			}
		}
		if (!flag) break;
	}

	if (flag) {
		//넓이 계산
		int min_y = min(y, 50);
		int max_y = max(y + n1 - 1, 49 + n2);
		int min_x = min(x, 50);
		int max_x = max(x + m1 - 1, 49 + m2);

		int area = (max_y - min_y + 1) * (max_x - min_x + 1);
		ans = min(ans, area);
	}
}
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n1 >> m1;
	for (int i = 0; i < n1; i++) {
		for (int j = 0; j < m1; j++) {
			char tmp; cin >> tmp;
			arr1[i][j] = tmp - '0';
		}
	}
	cin >> n2 >> m2;
	for (int i = 0; i < n2; i++) {
		for (int j = 0; j < m2; j++) {
			char tmp; cin >> tmp;
			arr2[i][j] = tmp - '0';
		}
	}

	//퍼즐 2는 가운데 고정시켜두기  
	// -> 현재 퍼즐의 각 꼭지점 : (50, 50), (50, 49 + m2), (49 + n2, 50), (49 + n2, 49 + m2) 
	for (int i = 50; i < 50 + n2; i++) {
		for (int j = 50; j < 50 + m2; j++) {
			arr[i][j] = arr2[i - 50][j - 50];
		}
	}


	//for 1 : 퍼즐을 돌리면서 확인 (총 4번)
	//for 2 : 해당 퍼즐의 첫 칸을 (0, 0) ~ (100, 100) 까지 위치시키며 비교
	for (int k = 0; k < 4; k++) {
		rotate();
		for (int i = 0; i < 100; i++) {
			for (int j = 0; j < 100; j++) {
				go(i, j);
			}
		}
	}

	cout << ans << "\n";
	return 0;
}