[백준/BOJ] 백준 20002번 : 사과나무

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

20002번: 사과나무

2차원 누적합을 만들고, 수확할 수 있는 모든 구간을 확인하여 문제를 해결했다.

 

코드

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

int n;
vector<vector<int>> board(305, vector<int>(305, 0));
vector<vector<int>> psum(305, vector<int>(305, 0));
int result = -987654321;

//2차원 누적합 만들기
void MakePsum()
{
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			psum[i][j] = psum[i][j - 1] + psum[i - 1][j] - psum[i - 1][j - 1] + board[i][j];
		}
	}
}

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

	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			int input;
			cin >> input;

			board[i][j] = input;
		}
	}

	MakePsum();

	for (int k = 1; k <= n; k++)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				pair<int, int> point1 = make_pair(i, j);
				pair<int, int> point2 = make_pair(i + k - 1, j + k - 1);

				if (point2.first > n || point2.second > n)
					continue;

				int this_result = psum[point2.first][point2.second] - psum[point2.first][point1.second - 1] - psum[point1.first - 1][point2.second] + psum[point1.first - 1][point1.second - 1];

				result = max(result, this_result);
			}
		}
	}

	cout << result;

	return 0;
}