51. 영지 (territory) 선택 (large : 2차원 배열 구간합 : 제한시간 1초 : DP)

나의정답1.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int main(int argc, char** argv) {
	freopen("input.txt", "rt", stdin);

	int i, j, n, m, H, W, row, col, sum = 0, max = -1;
	scanf("%d %d", &row, &col);
	int** arr = new int* [row];
	for (i = 0; i < row; i++)
		arr[i] = new int[col];

	for (i = 0; i < row; i++) {
		for (j = 0; j < col; j++) {
			scanf("%d", &arr[i][j]);
		}
	}

	scanf("%d %d", &H, &W);

	for (i = 0; i <= row - H; i++) {
		sum = 0;
		for (j = 0; j <= col - W; j++) {
			if (j == 0) {
				for (n = i; n < i + H; n++) {
					for (m = j; m < j + W; m++) 
						sum += arr[n][m];
				}		
			}
			else {
				for (n = i; n < i + H; n++) {
					sum -= arr[n][j - 1];
					sum += arr[n][j + W - 1];
				}
			}
			if (sum > max) {
				max = sum;
			}
		}
	}

	printf("%d", max);

	for (i = 0; i < row; i++)
		delete[] arr[i];
	delete[] arr;

	
}

 

나의정답2. 동적테이블 활용

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);

	int i, j, H, W, row, col, tempRow, tempCol, sum = 0, max = -1;
	scanf("%d %d", &tempRow, &tempCol);
	row = tempRow + 1;
	col = tempCol + 1;
	int** arr = new int* [row];

	for (i = 0; i < row; i++)
		arr[i] = new int[col];

	int** dy = new int* [row];
	for (i = 0; i < row; i++)
		dy[i] = new int[col];

	for (i = 0; i < row; i++) {
		for (j = 0; j < col; j++) {
			if (i == 0 || j == 0)
				arr[i][j] = 0;
			else {
				scanf("%d", &arr[i][j]);
			}			
		}
	}
	for (i = 0; i < row; i++) {
		for (j = 0; j < col; j++) {
			if (i == 0 || j == 0)
				dy[i][j] = 0;
			else {
				dy[i][j] = dy[i - 1][j] + dy[i][j - 1] - dy[i - 1][j - 1] + arr[i][j];
			}
		}
	}

	scanf("%d %d", &H, &W);

	for (i = H; i < row; i++) {
		for (j = W; j < col; j++) {
			sum = dy[i][j] - dy[i - H][j] - dy[i][j - W] + dy[i - H][j - W];
			if (sum > max)
				max = sum;
		}
	}

	printf("%d", max);

	for (i = 0; i < row; i++)
		delete[] arr[i];
	delete[] arr;

	for (i = 0; i < row; i++)
		delete[] dy[i];
	delete[] dy;
	
}