취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 11380번 문제인 Hole in the Wall이다.

문제는 아래 링크를 확인하자.

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

벽돌이 차지하는 "칸"이 아닌, 벽돌이 놓여 만들어진 "테두리"에 초점을 맞춰 문제를 해결하자.

먼저 두 가로줄을 고정해보자. 그리고, 이 두 가로줄의 일부를 각각 윗변과 아랫변으로 하는 최대 직사각형의 넓이를 구해보자. 이를 빠르게 구하기 위해 위 가로줄의 각 격자점에서 세로방향으로 아래 가로줄까지 변이 이어질 수 있는지를 빠르게 계산할 수 있게끔 각 격자점에서 아래방향으로 최대로 뻗을 수 있는 거리를 전처리해두자. 이는 O(N^2)으로 간단히 할 수 있다.

두 가로줄은 중간에 세로방향으로 놓인 벽돌이 있어 중간에 끊어진 곳이 존재할 수 있고, 끊어진 부분을 포함하는 직사각형은 존재하지 않다는 점에 유념하며 O(N) sweeping으로 하나의 가로줄쌍에 대한 답안을 구해낼 수 있다.

모든 창문은 윗변과 아랫변이 존재한다. 따라서, 가능한 모든 윗변과 아랫변 쌍, 즉 두 가로줄 쌍에 대해 위의 과정을 반복하는 것으로 문제를 해결할 수 있다. 이렇게 구현할 시 최종 시간복잡도는 O(N^3)이 된다. 사칙연산 외에 별다른 연산이 없고 제한시간이 3초로 넉넉하므로 이는 충분히 돌아갈 수 있는 시간복잡도이다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int table[1000][1000];
int clen[1000][1000];
bool rbrick[1000][1000];

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

	int N; cin >> N;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) cin >> table[r][c];
	}

	for (int c = 1; c < N; c++) {
		int len = 0;
		for (int r = N - 1; r > 0; r--) {
			clen[r][c] = len;
			if (table[r - 1][c - 1] == table[r - 1][c]) len = 0;
			else len++;
		}
	}

	for (int r = 1; r < N; r++) {
		for (int c = 1; c < N; c++) {
			if (table[r - 1][c] == table[r][c]) rbrick[r][c] = 1;
		}
	}

	int ans = 0, fr = 0, fc = 0, sr = 0, sc = 0;

	for (int r1 = 1; r1 < N; r1++) {
		for (int r2 = r1 + 1; r2 < N; r2++) {
			int cdist = r2 - r1;
			int sign = 0;
			for (int c = 1; c < N; c++) {
				if (clen[r1][c] >= cdist) {
					if (sign) {
						int area = (c - sign) * cdist;
						if (ans < area) {
							ans = area, fr = r1, fc = sign, sr = r2, sc = c;
						}
					}
					else sign = c;
				}
				if (rbrick[r1][c] || rbrick[r2][c]) sign = 0;
			}
		}
	}

	cout << ans << ' ' << fr + 1 << ' ' << fc + 1 << ' ' << sr << ' ' << sc;
}