[백준/7573/파이썬] 고기 잡이

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

7573번: 고기잡이

Problem

•  물고기를 잡을 수 있는 곳과 여기서 고기잡이 배가 사용할 수 있는 그물의 폭에 제한을 두었다.
• 고기를 잡을 수 있는 영역, 물고기의 위치, 그물의 폭이 주어졌을 때 한 번의 그물치기로 잡을 수 있는 가장 많은 물고기의 마릿수를 구하는 프로그램을 작성하시오.

조건

• 그물은 길이가 l인 직선으로 생각할 수 있고, 물고기를 잡을 때, 그물은 한 변의 길이가 1 이상 정수인 직사각형 모양으로 치게 된다. 예를 들어, l = 10이라면, 칠 수 있는 그물의 모양은 1×4, 2×3, 3×2, 4×1과 같이 4가지 형태의 직사각형이 된다. 
• 고기를 잡을 수 있는 곳은 N×N 크기의 모눈종이 모양으로 되어 있다. 각 모눈에는 좌표가 주어지며, 가장 왼쪽 위 모눈이 (1,1)이고, 가장 오른쪽 아래 모눈이 (N,N)이다.
• 고기잡이 배는 한 모눈 위에 위치를 잡고 자신의 오른쪽과 아래쪽으로 그물을 친다.일단 그물을 치면, 그물 안, 그리고 그물에 걸친 물고기들을 잡을 수 있다.
• 고기를 잡을 수 있는 영역 밖으로 그물을 치는 경우는 없다.
• 첫 번째 줄에는 모눈종이의 크기, 그물의 길이, 물고기의 수를 나타내는 세 개의 정수 N, l, M이 하나의 공백을 두고 주어진다. 단, 2 ≤ N ≤ 10,000, 4 ≤ l ≤ 100, 1 ≤ M ≤100 이다.
•  l은 l ≤ 4N - 4을 만족하는 짝수

SOL

상당히 구현할게 많은 문제이다 . 

구현이 많은 문제는 당황하지 않고, 조건을 하나씩, 하나씩 나눠서 구현해야한다. 우선, 모든 모눈종이에 대해서 반복을 돌면 안된다. N^2만 되어도, 10^10이기 때문에, TL이 된다.

1. 그물의 길이가 L인 직선으로 만들 수 있는, 그물을 구하는 함수.
   • 그물의 길이가 L일 때, L은 짝수이고, 만들 수 있는 그물은 반복문 1개면 쉽게 구할 수 있다.
2. 그물을 치는(고기를 잡는) 함수
   • 그물의 최대 경우의 수는 50가지가 나올 수 있다. L=50, (1*49,2*48,3*47...25*25....49*1) 등
   • 물고기가 최대 100개 , 그물치는 경우의수는 최대 50가지, 구현할 때, O(MN)꼴로 나타내야한다. 잘못해서 O(M^N)꼴로 나타내는 실수를 하면 안된다.
     
   • 물고기 있는 곳에서 그물을 친다고 가정했을때, 그 물고기가 그물에 끝점에 걸려있는 경우까지 다 봐주면 된다.즉, 아래의 그림과 같이, 그물을 움직여주면 된다! 그물의 시작점을 옮겨준다고 생각하면 편하다.(내가 시작한 물고기를 가장자리에 걸치게 하기 위해서)

예를들어, 내가 (4,5)에 있는 물고기를 시작으로 , (2,3)짜리 그물을 펼치려고 하면, 

Y : (4,5)에서 그물을 펼쳐보고, (3,5) 에서 펼쳐보고, (2,5)에서 펼쳐보고 ,

X : (4,4)에서 펼쳐보고, (4,3)에서 펼쳐보고, (4,2)에서 펼쳐보는 식으로 구현했다.

import sys
input = sys.stdin.readline
N,L,M = map(int,input().split())
fish=[]

# 그물의 크기별로 구하는 함수
def getNet(nL):
    half_nL= nL//2
    nets=[]
    for i in range(1,half_nL):
        nets.append((i,half_nL-i))
    return nets

#그물을 칠 수 있는 범위 chk
# zero-base가 아니기 때문에, N 포함 xx
def is_valid_coord(y,x,net):
    if y+net[0]>N or x+net[1]>N:
        return False
    else:
        return True
# 그물의 범위 안에, 물고기들이 몇마리가 있는지 확인해준다.
def cntFish(y,x,net):
    if not is_valid_coord(y,x,net):
        return 0
    fcnt= 0
    for fh in fish:
        fy,fx=fh
        if y<=fy<=y+net[0] and x<=fx<=x+net[1]:
            fcnt+=1
    return fcnt

def getFish(net):
    maxfish=0
    for fh in fish:
        y,x = fh
        for ny in range(y,y-net[0]-1,-1):
            maxfish=max(maxfish,cntFish(ny,x,net))
        for nx in range(x,x-net[1]-1,-1):
            maxfish=max(maxfish,cntFish(y,nx,net))
    return maxfish

for _ in range(M):
    y,x=map(int,input().split())
    fish.append((y,x))

def solve():
    nets = getNet(L)
    ans=0
    for net in nets:
        ans =max(ans,getFish(net))
    print(ans)

solve()