[BOJ 27285 // C++] L-Board

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

 

이번에 볼 문제는 백준 27285번 문제인 L-Board이다.
문제는 아래 링크를 확인하자.

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

27285번: L-Board

각 칸 (r,c)에 대하여, 해당 칸부터 왼쪽으로 연속한 칸의 수의 합으로 가능한 최댓값을 dpL[r][c], 오른쪽으로 연속한 칸의 수의 합으로 가능한 최댓값을 dpR[r][c], 위쪽과 아랫쪽의 방향으로 이와 같은 값을 dpU[r][c], dpD[r][c]라 하자. 이와 같은 값을 모두 알고 있다면 배열의 모든 칸에 대하여 그 칸을 중심으로 하는 L-Board에 적힌 수의 합을 최댓값을 구해보는 것으로 문제를 해결할 수 있게 된다.

 

dpL[r][c]의 값은 dpL[r][c-1]이 양수이면 dpL[r][c-1] + ((r,c)에 적힌 수)와 같이 나타나고 그렇지 않다면 그냥 (r,c)에 적힌 수와 같아짐을 관찰하자. 이와 같은 점화식을 이용하면 모든 dpL[r][c]의 값을 O(전체 칸 수)에 계산해낼 수 있다. 이는 dpR,dpU,dpD 또한 마찬가지이다.

 

주어지는 칸의 개수의 최댓값은 100만개이므로 위와 같은 방법을 이용해 문제를 제한시간 내에 충분히 해결할 수 있다.

 

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

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

int R, C;
ll board[1000][1000];
ll dpL[1000][1000], dpR[1000][1000], dpU[1000][1000], dpD[1000][1000];
ll ans = -1000000007;

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

	cin >> R >> C;
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			cin >> board[r][c];
		}
	}

	for (int r = 0; r < R; r++) {
		dpL[r][0] = board[r][0];
		for (int c = 1; c < C; c++) {
			dpL[r][c] = max(dpL[r][c - 1], 0LL) + board[r][c];
		}
	}
	for (int r = 0; r < R; r++) {
		dpR[r][C - 1] = board[r][C - 1];
		for (int c = C - 2; c > -1; c--) {
			dpR[r][c] = max(dpR[r][c + 1], 0LL) + board[r][c];
		}
	}
	for (int c = 0; c < C; c++) {
		dpU[0][c] = board[0][c];
		for (int r = 1; r < R; r++) {
			dpU[r][c] = max(dpU[r - 1][c], 0LL) + board[r][c];
		}
	}
	for (int c = 0; c < C; c++) {
		dpD[R - 1][c] = board[R - 1][c];
		for (int r = R - 2; r > -1; r--) {
			dpD[r][c] = max(dpD[r + 1][c], 0LL) + board[r][c];
		}
	}

	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			ans = max(ans, max(dpU[r][c], dpD[r][c]) + max(dpL[r][c], dpR[r][c]) - board[r][c]);
		}
	}

	cout << ans;
}