사과나무
문제 해석
NxN크기의 과수원에서 KxK 범위의 최대 순수익(수익-인건비)을 구하는 문제입니다.
각 좌표에 순수익이 적힌 2차원 배열 정보가 주어집니다.
설계(10)
먼저 Naive하게 K를 정하고(O(N)) 만들 수 있는 모든 KxK를 일일히 구해가면서 더해주는 방식을 생각할 수 있습니다. 이럴 경우 O(N^4)정도로 시간안에 통과가 불가능합니다.
그러나, Naive한 방법에서 약간 최적화를 해주면 시간안에 통과가 가능합니다. 바로 누적합 방법을 이용하는 것입니다.
누적합을 이용하면 Naive방법에서 중복되는 작업인 해당 범위의 수익의 합을 구하는 과정을 없앨 수 있습니다.
이후에 가능한 모든 범위를 만들어서 최댓값을 갱신시켜주면 됩니다.
이로써, 최악의 경우(N=300) 300x300+299x299…+1x1=약 O(10^7)으로 시간안에 통과가 가능합니다.
구현(10)
코드
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 301
int arr[MAXN][MAXN];
int N;
int ans=-1000;
int calc(int x1, int y1, int x2, int y2) {
return arr[x2][y2] - arr[x1 - 1][y2] - arr[x2][y1 - 1] + arr[x1 - 1][y1 - 1];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
cin >> arr[i][j];
arr[i][j] += arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1];
}
}
for (int k = 1; k <= N; k++) {
for (int i = 1; i <= N - k + 1; i++) {
for (int j = 1; j <= N - k + 1; j++) {
ans = max(ans, calc(i, j, i+k-1, j+k-1));
}
}
}
cout << ans << "\n";
return 0;
}
디버깅
제출결과
16ms
마무리
누적합 방법을 이용한 최적화 관련 문제였습니다. 다소 많이 보이는 유형이므로 쉽게 풀이할 수 있었습니다.