취미로 코딩하기

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

이번에 볼 문제는 백준 2874번 문제인 검정 직사각형이다.
문제는 아래 링크를 확인하자.

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

격자 위에서의 두 겹치지 않는 직사각형은 (1)어떤 행방향 경계선을 기준으로 두 직사각형이 서로 다른 쪽에 존재하거나 (2)어떤 열방향 경계선을 기준으로 두 직사각형이 서로 다른 쪽에 존재한다. (물론 둘 모두에 해당할 수도 있다.) 따라서 문제의 답은 행방향 경계선으로 나누어 두 직사각형을 넣는 경우의 수와 열방향 경계선을 기준으로 나누어 두 직사각형을 넣는 경우의 수의 합에서 두 경계선 모두로 나누어 직사각형을 넣는 경우의 수를 빼는 것으로 구할 수 있다.

위 각각의 경우의 수는 각 칸을 기준으로 해당 칸을 좌상단, 좌하단, 우상단, 우하단 칸으로 갖는 경우의 수 및 그 값들의 적절한 2차원 누적합을 전처리한 후 스위핑하는 것으로 빠르게 계산할 수 있다. 글쓴이는 각 경우의 수를 스택을 이용한 히스토그램 문제 풀이법을 이용해 계산하였다. (이 문제에 히스토그램이 어디에 있는지 모르겠다면, 각 행을 기준으로 그 행의 밑바닥(?)에 붙어있는 위쪽 열방향으로 연속한 검정 칸모양을 그려보면 히스토그램과 같음을 알 수 있을 것이다. 이 아이디어는 의외로 곳곳에서 활용되므로 기억해두는 것이 좋다.)

10007로 나눈 나머지를 구하라는 조건을 놓쳐 몇 번 틀렸다(...). 항상 문제가 요구하는 것을 주의깊게 읽자.

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

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

int N;
char board[1002][1002];
int LU[1002][1002], RU[1002][1002], LD[1002][1002], RD[1002][1002];
int H[1002];

vector<pair<int, int>> stk; // {높이, 길이}
int ans;

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

	cin >> N; stk.reserve(N);
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			cin >> board[r][c];
		}
	}
	
	memset(H, 0, sizeof(H));
	for (int r = 1; r <= N; r++) {
		int psum = 0;
		stk.clear();
		for (int c = 1; c <= N; c++) {
			int &h = H[c];
			if (board[r][c] == 'C') h++;
			else h = 0;
			int len = 1;
			while (!stk.empty() && stk.back().first >= h) {
				len += stk.back().second;
				psum -= stk.back().first * stk.back().second;
				stk.pop_back();
			}
			psum += h * len;
			stk.emplace_back(make_pair(h, len));
			LU[r][c] = (max(psum - 1, 0) + LU[r - 1][c] + LU[r][c - 1] - LU[r - 1][c - 1]) % 10007;
		}
	}

	memset(H, 0, sizeof(H));
	for (int r = 1; r <= N; r++) {
		int psum = 0;
		stk.clear();
		for (int c = N; c > 0; c--) {
			int &h = H[c];
			if (board[r][c] == 'C') h++;
			else h = 0;
			int len = 1;
			while (!stk.empty() && stk.back().first >= h) {
				len += stk.back().second;
				psum -= stk.back().first * stk.back().second;
				stk.pop_back();
			}
			psum += h * len;
			stk.emplace_back(make_pair(h, len));
			RU[r][c] = (max(psum - 1, 0) + RU[r - 1][c] + RU[r][c + 1] - RU[r - 1][c + 1]) % 10007;
		}
	}

	memset(H, 0, sizeof(H));
	for (int r = N; r > 0; r--) {
		int psum = 0;
		stk.clear();
		for (int c = N; c > 0; c--) {
			int &h = H[c];
			if (board[r][c] == 'C') h++;
			else h = 0;
			int len = 1;
			while (!stk.empty() && stk.back().first >= h) {
				len += stk.back().second;
				psum -= stk.back().first * stk.back().second;
				stk.pop_back();
			}
			psum += h * len;
			stk.emplace_back(make_pair(h, len));
			RD[r][c] = (max(psum - 1, 0) + RD[r + 1][c] + RD[r][c + 1] - RD[r + 1][c + 1]) % 10007;
		}
	}

	memset(H, 0, sizeof(H));
	for (int r = N; r > 0; r--) {
		int psum = 0;
		stk.clear();
		for (int c = 1; c <= N; c++) {
			int &h = H[c];
			if (board[r][c] == 'C') h++;
			else h = 0;
			int len = 1;
			while (!stk.empty() && stk.back().first >= h) {
				len += stk.back().second;
				psum -= stk.back().first * stk.back().second;
				stk.pop_back();
			}
			psum += h * len;
			stk.emplace_back(make_pair(h, len));
			LD[r][c] = (max(psum - 1, 0) + LD[r + 1][c] + LD[r][c - 1] - LD[r + 1][c - 1]) % 10007;
		}
	}

	for (int r = 1; r < N; r++) {
		ans += (RU[r][1] - RU[r - 1][1]) * RD[r + 1][1];
		ans %= 10007;
	}
	for (int c = 1; c < N; c++) {
		ans += (LD[1][c] - LD[1][c - 1]) * RD[1][c + 1];
		ans %= 10007;
	}
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			ans -= (LU[r][c] - LU[r - 1][c] - LU[r][c - 1] + LU[r - 1][c - 1]) * RD[r + 1][c + 1];
			ans -= (LD[r][c] - LD[r + 1][c] - LD[r][c - 1] + LD[r + 1][c - 1]) * RU[r - 1][c + 1];
			ans %= 10007;
		}
	}
	ans %= 10007;
	if (ans < 0) ans += 10007;
	cout << ans;
}

#랜덤 마라톤 · 코스 9 H번