취미로 코딩하기

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

이번에 볼 문제는 백준 4011번 문제인 기름 파기이다.
문제는 아래 링크를 확인하자.

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

격자판 위의 서로 겹치지 않는 세 정사각형의 배치의 케이스를 나누어 문제를 해결할 수 있다.

구체적으로, 정사각형 세 개를 격자 위에 정했을 때 (1) 한 점을 기준으로 반직선 세 개를 그어 격자를 세 조각을 내 한 영역에 정사각형이 하나씩 들어가게 할 수 있거나 (2) 그렇지 않다면 평행선 두개를 그어 구분되는 세 영역에 정사각형이 하나씩 있게끔 할 수 있다.

2차원 prefix sum을 이용하여 K by K영역의 수의 합을 빠르게 계산해내자.

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

#include <iostream>
using namespace std;

int ans = 0;
int R, C, K;
int arr[1502][1502];
int psum[1502][1502];

int LU[1502][1502];
int RU[1502][1502];
int LD[1502][1502];
int RD[1502][1502];

int ROW[1502];
int rowL[1502], rowR[1502];
int COL[1502];
int colL[1502], colR[1502];

void init() {
	cin >> R >> C >> K;
	for (int r = 1; r <= R; r++) {
		for (int c = 1; c <= C; c++) cin >> arr[r][c];
	}

	//LU
	for (int r = 1; r <= R; r++) {
		for (int c = 1; c <= C; c++) {
			psum[r][c] = arr[r][c] + psum[r - 1][c] + psum[r][c - 1] - psum[r - 1][c - 1];
		}
	}

	for (int r = K; r <= R; r++) {
		for (int c = K; c <= C; c++) {
			LU[r][c] = max(psum[r][c] - psum[r - K][c] - psum[r][c - K] + psum[r - K][c - K], max(LU[r - 1][c], LU[r][c - 1]));
		}
	}
	
	//ROW
	for (int r = K; r <= R; r++) {
		for (int c = K; c <= C; c++) {
			ROW[r] = max(ROW[r], psum[r][c] - psum[r - K][c] - psum[r][c - K] + psum[r - K][c - K]);
		}
		rowL[r] = max(rowL[r - 1], ROW[r]);
	}

	for (int r = R; r >= K; r--) rowR[r] = max(rowR[r + 1], ROW[r]);

	//COL
	for (int c = K; c <= C; c++) {
		for (int r = K; r <= R; r++) {
			COL[c] = max(COL[c], psum[r][c] - psum[r - K][c] - psum[r][c - K] + psum[r - K][c - K]);
		}
		colL[c] = max(colL[c - 1], COL[c]);
	}

	for (int c = C; c >= K; c--) colR[c] = max(colR[c + 1], COL[c]);

	//RU
	for (int r = 1; r <= R; r++) {
		for (int c = C; c > 0; c--) {
			psum[r][c] = arr[r][c] + psum[r - 1][c] + psum[r][c + 1] - psum[r - 1][c + 1];
		}
	}

	for (int r = K; r <= R; r++) {
		for (int c = C - K + 1; c > 0; c--) {
			RU[r][c] = max(psum[r][c] - psum[r - K][c] - psum[r][c + K] + psum[r - K][c + K], max(RU[r - 1][c], RU[r][c + 1]));
		}
	}

	//LD
	for (int r = R; r > 0; r--) {
		for (int c = 1; c <= C; c++) {
			psum[r][c] = arr[r][c] + psum[r + 1][c] + psum[r][c - 1] - psum[r + 1][c - 1];
		}
	}

	for (int r = R - K + 1; r > 0; r--) {
		for (int c = K; c <= C; c++) {
			LD[r][c] = max(psum[r][c] - psum[r + K][c] - psum[r][c - K] + psum[r + K][c - K], max(LD[r + 1][c], LD[r][c - 1]));
		}
	}

	//RD
	for (int r = R; r > 0; r--) {
		for (int c = C; c > 0; c--) {
			psum[r][c] = arr[r][c] + psum[r + 1][c] + psum[r][c + 1] - psum[r + 1][c + 1];
		}
	}

	for (int r = R - K + 1; r > 0; r--) {
		for (int c = C - K + 1; c > 0; c--) {
			RD[r][c] = max(psum[r][c] - psum[r + K][c] - psum[r][c + K] + psum[r + K][c + K], max(RD[r + 1][c], RD[r][c + 1]));
		}
	}
	
}

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

	init();

	// 가로3분할, 세로3분할
	for (int r = K * 2; r <= R - K; r++) {
		ans = max(ans, ROW[r] + rowL[r - K] + rowR[r + K]);
	}
	for (int c = K * 2; c <= C - K; c++) {
		ans = max(ans, COL[c] + colL[c - K] + colR[c + K]);
	}

	//LU 조각이 있는 분할
	for (int r = K; r <= R - K; r++) {
		for (int c = K; c <= C - K; c++) {
			ans = max(ans, max(LU[r][c] + RU[r][c + 1] + RD[r + 1][1], LU[r][c] + LD[r + 1][c] + RD[1][c + 1]));
		}
	}
	
	//RD 조각이 있는 분할
	for (int r = K + 1; r <= R - K + 1; r++) {
		for (int c = K + 1; c <= C - K + 1; c++) {
			ans = max(ans, max(RD[r][c] + LD[r][c - 1] + LU[r - 1][C], RD[r][c] + RU[r - 1][c] + LU[R][c - 1]));
		}
	}

	cout << ans;
}