[BOJ] 백준 7573 고기잡이

출처: https://www.acmicpc.net/problem/7573

 Input 

7 10 6

2 2

2 4

6 2

7 4

3 3

5 6

 

 Output 

3

 

[Jungol] 1437 같은 모양 찾기문제와 달리 그물의 크기가 변합니다.

[Jungol] 정올 1437 같은 모양 찾기

▶ 그물의 크기는 길이 L에서 만들 수 있는 사각형 입니다.

   ex) L = 10일 때, 1×4, 2×3, 3×2, 4×1 

      → (초기) 한 변의 모서리(l1) = 1, 다른 모서리의 길이(l2) = (L - (2 x l1)) / 2 = (10 - 2) / 2 = 4

      → l1++; l2--;를 하면서 그물의 크기 조정

▶ 이중 for문을 구현하지 않고도 영역내의 물고기 수를 파악할 수 있습니다.

그물의 (sx, sy)와 (ex, ey) 좌표와 물고기의 위치 (x, y) 알고 있다면 아래와 같이 계산할 수 있습니다.

▶그물의 크기를 정하고 (sx, sy) 위치를 탐색할 때, 모든 지점을 탐색하면 TLE 발생

위와 같이 (4, 3)에서 그물을 치는 것은 비효율 적입니다.

▶ 어디를 (sx, sy)로 설정하는 것이 좋을까요?

물고기가 존재하는 위치 & 물고기간의 교차점

※ (2, 3)과 (4, 5)과 주어질 때 두 좌표의 교차점은  (4, 3)과 (2, 5) 입니다.

※ 모눈종이 크기를 int형 이차원 배열로 잡을 시 메모리 초과가 발생하기 때문에 char[][] 이용

※ 그물의 한변의 길이가 l 일때 실제 물고기가 잡히는 범위는 l + 1입니다.

    (물고기가 놓인 위치가 각 모눈종이 꼭지점에 위치하기 때문)

---

#include <stdio.h>
 
const int MAX_N = 10000;
const int MAX_M = 100;
int ans, N, L, M, idx;
char section[MAX_N + 5][MAX_N + 5];
struct Node {
    int x, y;
}fish[MAX_M], chk[MAX_M * MAX_M];
 
void fishing(int sx, int sy, int l1, int l2) {
    int cnt = 0;
    int ex = sx + l1, ey = sy + l2;
    // 잡을 수 있는 물고기 개수 확인
    for (int i = 0; i < M; ++i) {
        if (sx <= fish[i].x && fish[i].x <= ex &&
            sy <= fish[i].y && fish[i].y <= ey)
            cnt++;
    }
    // 가장 많이 잡은 경우
    ans = ans < cnt ? cnt : ans;
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%d %d %d", &N, &L, &M);
    for (int i = 0; i < M; ++i) {
        scanf("%d %d", &fish[i].x, &fish[i].y);
        // 물고기가 존재하는 위치 설정
        section[fish[i].x][fish[i].y] = 'Y';
        chk[idx++] = { fish[i].x, fish[i].y };
 
    }
 
    // 중복여부를 확인하면서 물고기들 교차점 위치 확인 
    for (int i = 0; i < M - 1; ++i) {
        for (int j = i; j < M; ++j) {
            if (section[fish[i].x][fish[j].y] != 'Y') {
                chk[idx++] = { fish[i].x, fish[j].y };
                section[fish[i].x][fish[j].y] = 'Y';
            }
            if (section[fish[j].x][fish[i].y] != 'Y') {
                chk[idx++] = { fish[j].x, fish[i].y };
                section[fish[j].x][fish[i].y] = 'Y';
            }
        }
    }
 
    int l1 = 1, l2 = (L - 2) / 2;
    while (l2 > 0) {
        for (int i = 0; i < idx; ++i) {
            // 찾은 교차점과 물고기 위치에서 그물 치기
            fishing(chk[i].x, chk[i].y, l1, l2);
        }
        l1++; l2--;
    }
    printf("%d\n", ans);
}