[C/C++] 백준 - 20002번 : 사과나무

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

20002번: 사과나무

문제

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

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

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

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

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

 

N의 최대 크기가 300이기 때문에 누적합으로 값만 가져오고 모든 경우의 수를 확인해주어도 시간 내 해결이 가능하다.

누적합 + 완전탐색 알고리즘으로 해결하였다.

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <set>
#include <map> 
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long	
#define ull unsigned long long
#define INF 987654321
#define Mod 100000
#define endl '\n'
#define pil pair<int,int>

using namespace std;

int N;
const int MAX = 300;
int board[MAX + 1][MAX + 1];
int psum[MAX + 1][MAX + 1];

void input() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> board[i][j];
			psum[i][j] = psum[i][j - 1] + board[i][j];
		}
	}
}

bool isValid(int y, int x, int k) {
	return (y + k - 1 <= N && x + k - 1 <= N);
}

int ret(int y, int x, int k) {
	int sum = 0;
	for (int i = 0; i < k; i++) {
		sum += psum[y+i][x + k - 1] - psum[y+i][x - 1];
	}
	return sum;
}

int solution() {
	int answer = -INF;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			for (int k = 1; k <= N; k++) {
				if (!isValid(i, j, k)) break;
				answer = max(answer, ret(i, j, k));
			}
		}
	}
	return answer;
}

int main() {
	fastio;
	input();
	cout << solution() << endl;

	return 0;
}