귀농
문제 해석
- 현수가 상근이와 선영이에게 땅을 빌려주었을 때, 각 두사람의 농사지을 땅의 수익의 합이 같은 경우의 수를 구하는 문제입니다.
- 땅을 나누어줄 때, 두개의 땅은 꼭지점 하나가 맞닿아 있습니다.
설계(X)
- 처음에 생각한 방법은 첫번째 땅의 양 꼭지점(O(N^4))을 정한 후, 두번째 땅의 꼭지점을 정하는(O(N^2)) 방식으로 구현하였습니다.
- 하지만, 시간복잡도는 총 O(N^6)으로 시간초과가 발생합니다.
- 시간복잡도를 줄이는 방안을 마땅히 찾지 못하여 세진짱님의 블로그를 통해 아이디어를 얻을 수 있었습니다.
- 키포인트는 두개의 땅이 맞닿는 꼭지점을 정한 후 (O(N^2)), 위쪽과 아래쪽 땅의 크기를 각각 정해서(O(N^2)) 맞는 조건의 경우의 수를 구하는 것입니다.
- 위쪽의 땅의 수익의 합을 map자료구조에 저장한 후, 아래쪽 땅의 수익의 합을 계산하여 맞는 경우의 수를 구하면 원하는 결과를 얻을 수 있습니다.
- 위쪽의 땅과 아래쪽 땅이 생긴 모양은 두가지가 있는데, 위쪽의 오른쪽과 아래쪽의 왼쪽, 위쪽의 왼쪽과 아래쪽의 오른쪽 각 두가지를 생각할 수 있습니다.
- 원하는 범위의 수익의 합은 전처리로 psum배열에 누적합을 저장해 놓는 방법으로 O(1)만에 구할 수 있습니다.
- map자료구조를 사용하기 때문에 총 시간복잡도는 O(N^4xlog(N))으로 시간안에 실행이 가능합니다.
- map을 이용하지 않고, 정적 배열을 선언하여 카운팅소트 기법을 이용하면 O(N^4)으로 최적화를 시킬 수 있습니다.(단, 메모리 사용량은 크게 증가합니다).
구현(X)
코드1(map 이용)
#include <iostream>
#include <map>
using namespace std;
#define MAXN 51
int arr[MAXN][MAXN];
int psum[MAXN][MAXN];
int N;
int ans;
int Sum(int x1, int y1 ,int x2, int y2){
return psum[x2][y2] - psum[x2][y1-1] - psum[x1-1][y2] + psum[x1-1][y1-1];
}
map<int,int> mp;
void check(int x, int y){
mp.clear();
// 왼쪽위, 오른쪽 아래 사각형 체크
for (int i = x; i >= 1; i--){
for (int j = y; j >= 1; j--){
int sum = Sum(i,j,x,y);
if (mp.count(sum)==0) mp[sum] = 1;
else mp[sum]++;
}
}
for (int i = x+1; i <= N; i++){
for (int j= y+1; j<=N; j++){
int sum = Sum(x+1,y+1,i,j);
if (mp.count(sum)) {
ans += mp[sum];
}
}
}
mp.clear();
// 왼쪽 아래, 오른쪽 위 사각형 체크
for (int i = x; i >= 1; i--){
for (int j = y; j <=N; j++){
int sum = Sum(i,y,x,j);
if (mp.count(sum)==0) mp[sum] = 1;
else mp[sum]++;
}
}
for (int i = x+1; i<= N; i++){
for (int j = y-1; j >= 1; j--){
int sum = Sum(x+1,j,i,y-1);
if (mp.count(sum)) {
ans += mp[sum];
}
}
}
}
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];
}
}
for (int i = 1; i <=N; i++){
for (int j = 1; j <=N; j++){
psum[i][j] = arr[i][j] + psum[i-1][j] + psum[i][j-1]- psum[i-1][j-1];
}
}
for (int i = 1; i <= N; i++){
for (int j = 1; j <= N; j++){
check(i,j);
}
}
cout << ans <<"\n";
return 0;
}
코드2(배열 이용)
#include <iostream>
using namespace std;
#define MAXN 51
#define MID 1000 * 2500
int arr[MAXN][MAXN];
int psum[MAXN][MAXN];
int N;
int ans;
int cnt[MID*2+1];
int Sum(int x1, int y1 ,int x2, int y2){
return psum[x2][y2] - psum[x2][y1-1] - psum[x1-1][y2] + psum[x1-1][y1-1];
}
void check(int x, int y){
// 왼쪽위, 오른쪽 아래 사각형 체크
for (int i = x; i >= 1; i--){
for (int j = y; j >= 1; j--){
cnt[Sum(i,j,x,y)+MID]++;
}
}
for (int i = x+1; i <= N; i++){
for (int j= y+1; j<=N; j++){
ans += cnt[Sum(x+1,y+1,i,j)+MID];
}
}
for (int i = x; i >= 1; i--){
for (int j = y; j >= 1; j--){
cnt[Sum(i,j,x,y)+MID]--;
}
}
//memset(cnt,0,sizeof(cnt));
// 왼쪽 아래, 오른쪽 위 사각형 체크
for (int i = x; i >= 1; i--){
for (int j = y; j <=N; j++){
cnt[Sum(i,y,x,j)+MID]++;
}
}
for (int i = x+1; i<= N; i++){
for (int j = y-1; j >= 1; j--){
ans += cnt[Sum(x+1,j,i,y-1)+MID];
}
}
for (int i = x; i >= 1; i--){
for (int j = y; j <=N; j++){
cnt[Sum(i,y,x,j)+MID]--;
}
}
}
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];
}
}
for (int i = 1; i <=N; i++){
for (int j = 1; j <=N; j++){
psum[i][j] = arr[i][j] + psum[i-1][j] + psum[i][j-1]- psum[i-1][j-1];
}
}
for (int i = 1; i <= N; i++){
for (int j = 1; j <= N; j++){
check(i,j);
}
}
cout << ans <<"\n";
return 0;
}
디버깅
제출결과
- 코드1(map 사용) 메모리: 2140KB, 실행시간 : 564ms
- 코드2(배열 이용) 메모리: 21536KB, 실행시간 : 16ms
마무리
- 최적화를 하기위한 적절한 아이디어가 필요했던 구현 문제였습니다. 최적화할 방법을 찾지 못해 시간초과가 났습니다.
- 곰곰히 생각을 더 해보는 습관을 가질 필요가 있을 것 같습니다.