[백준 2829] 아름다운 행렬

문제 링크 => 2829번: 아름다운 행렬 (acmicpc.net)

2829번: 아름다운 행렬

---

Brute Force 문제이다.

 

부 대각선에 대한 합들을 미리 구하여 모든 주 대각선을 탐색하면서 미리 구한 값들을 빼는 방식으로 접근했다.

 

 

Solution Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <algorithm>
#include <string.h>
#include <cstring>
#include <queue>
#include <stack>
#define endl '\n'
#define INF 1000000000
#define ll long long

using namespace std;

int n, A[444][444];
int dp[444][444];

class Point {
public:
	int x, y;
	Point(int x, int y) {
		this->x = x;
		this->y = y;
	}
};

void input() 
{
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> A[i][j];
		}
	}
}

void makeDp(int upX, int upY, int downX, int downY) 
{
	int x = upX + 1, y = upY - 1, op = 0;
	while (1) {
		int thisSum = 0;
		Point* down, * up;
		if (op == 0) {
			y++;
			down = new Point(x, y);
			up = new Point(x - 1, y + 1);
		}
		else {
			thisSum = A[x][y+1];
			x++;
			down = new Point(x, y);
			up = new Point(x - 2, y + 2);
		}

		if (x > downX) break;
		
		while (up->x >= upX && down->x <= n && up->y <= n) {
			thisSum += (A[down->x][down->y] + A[up->x][up->y]);
			dp[up->x][up->y] = thisSum;
			down->x++, down->y--;
			up->x--, up->y++;
		}

		op = (op == 0 ? 1 : 0);
	}
}

void solve() 
{
	input();
	
	int result = -INF;
	for (int x = n - 1; x >= 1; x--) {
		int i, j, s = 1, t;
		makeDp(x, 1, n, 1 + (n - x));
		for (i = x; i <= n - 1; i++) {
			int thisSum = A[i][s];
			for (j = i + 1, t = s+1; j <= n; j++, t++) {
				thisSum += A[j][t];
				result = max(result, thisSum - dp[i][t]);
			}
			s++;
		}
	}
	for (int y = 2; y < n; y++) {
		int i, j, t, s = 1;
		makeDp(1, y, 1 + (n - y), n);
		for (i = 1; i <= n - y; i++) {
			int thisSum = A[s][y + s - 1];
			for (j = y + s, t = s + 1; j <= n; j++, t++) {
				thisSum += A[t][j];
				result = max(result, thisSum - dp[i][j]);
			}
			s++;
		}
	}

	cout << result << endl;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	solve();

	return 0;
}