[백준] 7573번 고기잡이 (Python)

백준 7573 고기잡이

단, 2 ≤ N ≤ 10,000, 4 ≤ l ≤ 100, 1 ≤ M ≤100 이다. l은 l ≤ 4N - 4을 만족하는 짝수이다. 완전 탐색하는 문제임을 금방 알 수 있었지만 방법을 제대로 설정하지 않으면 TLE가 나오는 문제다. 물고기들의 현재 위치가 그믈망의 경계선에 있어야 최댓값을 탐색하기에 유리하다. 시간 복잡도는 O((Ml)^2) 이다. 제한 시간은 1초로 100(물고기) 100 / 2(그물 경우의 수) 100(그물의 모든 경계) * 100(그물에 포함되는 물고기 탐색) 총 경우의 수가 약 5,0000,000으로 1억이 넘지 않으므로 TLE가 나지 않을 것이라고 예상할 수 있었다.

1. 모든 물고기의 위치에서
2. 가능한 모든 그물의 모양으로
3. 그물의 경계에 물고기가 있도록 그물을 펼친다
4. 그물의 왼쪽 위에 물고기 위치하도록 펼친 후, 한 칸 씩 이동한다.
5. 모든 물고기를 탐색하며 해당하는 그물 내에 몇 마리가 위치하는지 확인한다.

import sys
from functools import lru_cache

input = sys.stdin.readline

n, l, m = map(int, input().split())
nets = [[x, l // 2 - x] for x in range(1, l // 2)]
   
fishes = []

@lru_cache
def calc(tmpY, ty, tmpX, tx):
   cnt = 0
   for fy, fx in fishes:
       if tmpY >= fy >= ty and tmpX >= fx >= tx:
           cnt += 1
   return cnt


for _ in range(m):
   fishes.append(list(map(int, input().split())))

maxV = 0
for fy, fx in fishes:
   for ny, nx in nets:
       ty = fy
       tmpY = fy + ny
       tx = fx
       tmpX = fx + nx

       # 그물 왼쪽으로 이동
       for i in range(nx + 1):
           if n >= tmpY and ty >= 1 and n >= tmpX and tx >= 1:
               maxV = max(maxV, calc(tmpY, ty, tmpX, tx))
           if tx == 1:
               break
           tx -= 1
           tmpX -= 1
       
       # 그물 위로 이동
       for i in range(ny + 1):
           if n >= tmpY and ty >= 1 and n >= tmpX and tx >= 1:
               maxV = max(maxV, calc(tmpY, ty, tmpX, tx))
           if ty == 1:
               break
           ty -= 1
           tmpY -= 1

       # 그물 오른쪽으로 이동
       for i in range(nx + 1):
           if n >= tmpY and ty >= 1 and n >= tmpX and tx >= 1:
               maxV = max(maxV, calc(tmpY, ty, tmpX, tx))
           if tmpX == n:
               break
           tx += 1
           tmpX += 1
       
       # 그물 아래로 이동
       for i in range(ny + 1):
           if n >= tmpY and ty >= 1 and n >= tmpX and tx >= 1:
               maxV = max(maxV, calc(tmpY, ty, tmpX, tx))
           if tmpY == n:
               break
           ty += 1
           tmpY += 1
print(maxV)