알고리즘 문제풀기/인프런 강의 정답
51. 영지 (territory) 선택 (large : 2차원 배열 구간합 : 제한시간 1초 : DP)
코다람쥐
2022. 4. 22. 13:29
나의정답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;
}