[C++/1749] 점수 따먹기

---

⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.

---

누적합과 그에 대응하는 행렬크기를 완전탐색으로 문제를 해결했습니다. 누적합은 가장 유명한 DP임. 예전에 사과..어쩌구 문제에서 풀었던 문제와 매우 유사하고, 그 크기만 정의해주면 쉽게 풀리는 문제입니다. 아래는 정답 코드입니다. 

#include<iostream>

#define MAX 301
using namespace std;

int n,m, answer = -987654321, board[MAX][MAX], sum[MAX][MAX];

void init() {
	
	cin >> n >> m;
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> board[i][j];
		}
	}
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			sum[i][j] = board[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i-1][j-1];
		}
	}
	
}

int chk(int y, int x, int yLen, int xLen) {
	return sum[y + yLen - 1][x + xLen - 1] - sum[y + yLen - 1][x - 1] - sum[y - 1][x + xLen - 1] + sum[y - 1][x - 1];
}

void solve() {
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			for(int k = 1; k <= n && i + k - 1 <= n; k++){
				for(int l = 1; l <= m && j + l - 1 <= m; l++){
					answer = max(answer, chk(i,j,k,l));
				}
			}
		}
	}
	
}

int main() {
	
	init();
	solve();
	cout << answer;
	
	return 0;
}