[백준 20002] 사과나무 (C++)

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

문제

---

N × N 크기의 정사각형 모양 과수원이 있고, N × N 개의 사과나무가 1 × 1 크기의 간격으로 모든 칸에 심어져있다.

농부 형곤이가 가을을 맞아 사과를 수확하려는데, 땅주인 신영이가 "너는 과수원 내에 사과나무를 K × K 의 크기의 정사각형 모양으로만 수확해 가져갈 수 있어, 이때 K는 1보다 크거나 같고 N보다 작거나 같은 정수라구! 나머지는 내가 먹을께! 하하!" 라고 통보했다.

하나의 사과나무를 수확할 때, 사과를 통해 얻을 수 있는 이익과 노동비로 빠져나가는 손해가 동시에 이루어진다.

그래서 형곤이는 나무의 위치를 좌표로 하여, 사과를 통해 얻은 이익과 노동비를 더한 총이익을 2차원 배열의 형태로 정리했다.

악독한 땅주인 신영이로부터 고통받는 귀여운 형곤이에게 최대 총이익을 안겨주고 싶은 당신, 형곤이를 도와주자!

 

입력

---

첫 번째 줄에는 과수원의 크기 N이 주어진다. (1 ≤ N ≤ 300)

두 번째 줄부터 N + 1번째 줄까지, 해당 나무를 수확했을 때 얻을 수 있는 총이익을 표시한다.

총이익은 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

 

출력

---

첫 번째 줄에 최댓값을 출력한다.

 

문제 풀이

---

부분 합과 브루트 포스를 사용하는 문제.

arr[i][j]까지의 부분합 sums[i][j]는 arr[0][0]부터 arr[i][j]까지 만들어지는 직사각형 범위의 합이다.

arr가 다음과 같다면

a	b
c	d

부분합을 구하는 sums 배열은 다음과 같이 채워진다.

a	a+b
a+c	a+b+c+d

 

이 때 sums[1][1]인 a+b+c+d는 바로 윗 칸인 a+c와 바로 옆 칸인 a+c와 arr[1][1]을 합한 것에 a를 뺀 것과 같다. sums[0][1]과 sums[1][0]을 구할 때 a가 들어가게 되는데, 이 두 부분을 더하였으므로 a가 중복으로 들어갔기 때문이다. 따라서 중복으로 들어간 arr[0][0]을 빼주면 우리가 원하는 a+b+c+d를 구할 수 있다.

따라서 sums[i][j]는 sums[i-1][j]+sums[i][j-1]+arr[i][j]-sums[i-1][j-1]이라 할 수 있다.

이를 이용해 부분합 배열을 모두 채워준다.

이후 각 칸마다 모든 가능한 K의 범위 안에서 최댓값을 찾는다. 각 칸마다 가능한 K의 범위는 수확하는 모양이 정사각형이므로 1부터 i와 j 중 더 작은 값이 정사각형의 길이가 된다.

위의 sums 배열에서 arr[1][1]만을 얻어내고 싶다면 sums[1][1]에서 sums[0][1]과 sums[1][0]을 빼본다. 위의 설명과 마찬가지로 a가 중복으로 빠지게 되므로 추가로 sums[0][0]을 더하면 arr[1][1]을 얻어낼 수 있다. 따라서 오른쪽 아래가 i, j이면서 크기가 size인 정사각형의 합은 sums[i][j] - sums[i - size][j] - sums[i][j - size] + sums[i - size][j - size]가 된다.

 

아래는 코드.

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

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

	int N;
	cin >> N;
	int** arr = new int*[N];
	long long** sums = new long long*[N + 1];
	long long answer = -200000000;
	for (int i = 0; i < N+1; i++)
	{
		sums[i] = new long long[N + 1];
		for (int j = 0; j < N + 1; j++)
		{
			sums[i][j] = 0;
		}
	}
	for (int i = 0; i < N; i++)
	{
		arr[i] = new int[N];
		for (int j = 0; j < N; j++)
		{
			cin >> arr[i][j];
			sums[i + 1][j + 1] = sums[i+1][j] + sums[i][j+1] - sums[i][j]  + arr[i][j];
		}
	}
	for (int i = 1; i < N + 1; i++)
	{
		for (int j = 1; j < N + 1; j++)
		{
			int minLength = min(i, j);
			for (int size = 1; size <= minLength; size++)
			{
				long long  currentSum = sums[i][j] - sums[i - size][j] - sums[i][j - size] + sums[i - size][j - size];
				answer =  max(answer, currentSum);
			}
		}
	}
	cout << answer << "\n";
	return 0;
}