[BOJ 1184 // C++] 귀농

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

 

이번에 볼 문제는 백준 1184번 문제인 귀농이다.
문제는 아래 링크를 확인하자.

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

1184번: 귀농

한 변의 길이가 \(N\)인 땅에서는 직사각형 영역을 \(O(N^4)\)개 존재한다. 이러한 각 영역에 한번씩 접근하는 것으로 먼저 2차원 prefix sum 배열을 \(O(N^2)\)에 전처리해둔다면 각 \(r\)행 \(c\)열 칸을 좌상단, 우상단, 좌하단, 우하단 꼭짓점으로 갖는 직사각형이 가질 수 있는 "수익의 합"의 multiset을 모두 구할 수 있다.

 

이제, 각 칸에 대하여 문제에 주어지는 것과 같은 두 직사각형 영역이 존재하는 방식을 왼쪽위와 오른쪽아래에 하나씩 존재하는 경우 및 오른쪽위와 왼쪽아래에 하나씩 존재하는 경우로 나누어 만나는 중심별로 그 경우의 수를 구해 문제를 해결하자. 이는 정렬과 투포인터를 이용해 구현해낼 수 있다.

 

이와 같은 풀이의 시간복잡도는 \(O(N^4lgN)\)으로, 문제를 해결하기에 충분한 복잡도이다.

 

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

int N;
int arr[52][52];
int psum[52][52];
vector<int> vUL[52][52], vUR[52][52], vDL[52][52], vDR[52][52];

ll ans;

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

	cin >> N;
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			cin >> arr[r][c];
			psum[r][c] = arr[r][c] + psum[r - 1][c] + psum[r][c - 1] - psum[r - 1][c - 1];
		}
	}

	for (int r1 = 1; r1 <= N; r1++) {
		for (int c1 = 1; c1 <= N; c1++) {
			for (int r2 = r1; r2 <= N; r2++) {
				for (int c2 = c1; c2 <= N; c2++) {
					int val = psum[r2][c2] - psum[r1 - 1][c2] - psum[r2][c1 - 1] + psum[r1 - 1][c1 - 1];
					vUL[r2][c2].emplace_back(val);
					vUR[r2][c1].emplace_back(val);
					vDL[r1][c2].emplace_back(val);
					vDR[r1][c1].emplace_back(val);
				}
			}
		}
	}
	
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			sort(vUL[r][c].begin(), vUL[r][c].end());
			sort(vUR[r][c].begin(), vUR[r][c].end());
			sort(vDL[r][c].begin(), vDL[r][c].end());
			sort(vDR[r][c].begin(), vDR[r][c].end());
		}
	}

	for (int r = 1; r < N; r++) {
		for (int c = 1; c <= N; c++) {
			vector<int>& UL = vUL[r][c], & DR = vDR[r + 1][c + 1];
			int sUL = UL.size(), sDR = DR.size(), iUL = 0, iDR = 0;
			while (iUL < sUL && iDR < sDR) {
				if (UL[iUL] < DR[iDR]) iUL++;
				else if (UL[iUL] > DR[iDR]) iDR++;
				else {
					int val = UL[iUL];
					int cUL = 0, cDR = 0;
					while (iUL < sUL && UL[iUL] == val) cUL++, iUL++;
					while (iDR < sDR && DR[iDR] == val) cDR++, iDR++;
					ans += cUL * cDR;
				}
			}

			vector<int>& UR = vUR[r][c], & DL = vDL[r + 1][c - 1];
			int sUR = UR.size(), sDL = DL.size(), iUR = 0, iDL = 0;
			while (iUR < sUR && iDL < sDL) {
				if (UR[iUR] < DL[iDL]) iUR++;
				else if (UR[iUR] > DL[iDL]) iDL++;
				else {
					int val = UR[iUR];
					int cUR = 0, cDL = 0;
					while (iUR < sUR && UR[iUR] == val) cUR++, iUR++;
					while (iDL < sDL && DL[iDL] == val) cDL++, iDL++;
					ans += cUR * cDL;
				}
			}
		}
	}

	cout << ans;
}