사용한 알고리즘
알고리즘 설명
- 고기의 위치를 먼저 x축에 대해서 정렬한다.
- 정렬 뒤에 x축 맨 앞 고기부터 뒤쪽까지 모두 탐색한다.
- 고기의 그물의 가로와 세로를 정해야한다.
- 여기서 그물의 가로의 길이를 정하면 세로의 길이는 정해지므로 가로의 길이를 1~I-1까지 바꿔본다.
- y축의 높이는 그물이 맨 위쪽에 걸리는 경우부터 아래쪽에 걸리는 경우까지 모두 탐색한다.
- 이렇게 그물의 위치를 정한 뒤에 그 그물에 대해서 물고기가 몇마리나 걸리는지 계산한다.
- N과 M의 크기가 100이하이므로 O(N^4)에 대해서 성립한다.
풀이
// baekjoon 7573 yechan
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_M=101;
typedef pair<int, int> P;
int N, I, M, ans, x, y, i, j, a, b, bias, cur_x, cur_y, bottom_x, bottom_y, ret;
P fish[MAX_M];
int main() {
scanf("%d%d%d", &N, &I, &M);
for (int i=0; i<M; i++)
scanf("%d%d", &fish[i].first, &fish[i].second);
sort(fish, fish+M);
// 가로 세로 길이가 2번 중복되므로 나누기 2
I/=2;
// 모든 물고기 탐색
for (i=0; i<M; i++) {
x = fish[i].first;
y = fish[i].second;
// a 는 그물의 가로길이, b는 그물의 세로길이이다.
for (a=1; a<I; a++) {
// bias는 y축으로 그물을 어느정도 내릴지를 정하는 조건이다.
// 그물 밖으로 걸치는 경우를 탐색하기는 하지만, 어차피 물고기의 최대 조건은 그물이 밖으로 걸치지 않는 경우에 이미 만족한다.
for (bias=0; bias<=I-a; bias++) {
b = I-a;
cur_x = x;
cur_y = y - bias;
bottom_x = cur_x + a;
bottom_y = cur_y + b;
ret = 0;
// 그물의 위치가 정해지면 이 사이에 있는 물고기의 수를 계산한다.
for (j=i; j<M; j++) {
// 어차피 x축으로 정렬되어 있으므로 가로 길이 그물을 넘어가면 탐색 중지
if (bottom_x < fish[j].first) break;
// y축 사이에 존재하는지 판단.
if (cur_y <= fish[j].second && fish[j].second <= bottom_y) ret++;
}
ans = max(ret, ans);
}
}
}
printf("%d\n", ans);
return 0;
}
