[C++/20002] 사과나무

---

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

---

요즘 골드 4~5 문제를 푸는데, 이건 저번에 풀었었는데 solved에 로그인하지 않아서 이전에 풀었던 문제였던 것이였다. 하지만, 아주 새로운 방식으로 문제를 해결했다.

Dp + 구현으로 문제를 해결했습니다. 일단 N의 크기가 300이고 총 90,000이여도 1000만큼 곱해도 int의 범위를 벗어나지 않으니 상관이 없고, 대신 모든 정사각형의 범위를 다 따져야하기 때문에, 1부터 300까지 (0,0)부터, 전부를 뒤져봐야하기 때문에 단순 for문으로는 어마무시한 시간이 무조건 걸린다 판단해서, Dp인 누적합으로 미리 합을 구해놓고 문제를 해결했습니다. 오랜만에 Dp를 풀어보니까 아주 머리가 안돌아가서 큰일이었습니다. 천천히 다시 끌어올려야겠습니다.

아래는 정답 코드입니다.

#include<iostream>

#define MAX 301
using namespace std;

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

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

int isRange(int y, int x){
	return 1 <= y && y <= n && 1 <= x && x <= n;
}

int chk(int len, int y, int x){
	if(!isRange(y + len - 1, x + len -1)) return -1001;
	if(len == 1){
		return board[y][x];
	} else{
		return sum[y + len - 1][x + len - 1] - sum[y + len - 1][x - 1] - sum[y - 1][x + len - 1] + sum[y - 1][x - 1];
	}
}

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

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