[java 백준] 골드 4 / 7573번 고기잡이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
import static java.lang.Math.*;
 
public class Main {
 
    public static class Node{
        int x;
        int y;
        public Node(int x,int y){
            this.x=x;
            this.y=y;
        }
    }
 
    public static int N;
    public static int I;
    public static int M;
    public static ArrayList<Node>fish=new ArrayList<>();
 
    public static int count=0;
 
    public static void search(int x,int y,int netX,int netY){
        // 물고기 인덱스 가져옴
        // 0 1 1 4 가 들어왔을 때
 
        int cnt=0;
 
        for(int i=0;i<M;i++){
            if(fish.get(x).x<=fish.get(i).x&&fish.get(i).x<=fish.get(x).x+netX&&fish.get(y).y<=fish.get(i).y&&fish.get(i).y<=fish.get(y).y+netY){
                cnt++;
            }
 
        }
        count=Math.max(count,cnt);
 
 
    }
 
 
 
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        // 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine()) ;
        N = Integer.parseInt(st.nextToken());
        I = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
 
        for(int i=0;i<M;i++){
            st=new StringTokenizer(br.readLine());
            int x=Integer.parseInt(st.nextToken());
            int y=Integer.parseInt(st.nextToken());
            fish.add(new Node(x,y));
        }
 
 
        // 물고기를 기준으로 생각해줬어야함! (지금까지는 그물을 기준으로 생각했었음!)
        // 그물의 테두리에 물고기가 걸치게 끔 생각했어야함
 
        for(int i=0;i<M;i++){
            for(int j=0;j<M;j++){
                // 물고기 2개를 골라줌
                for(int k=1;k<I/2;k++){
                    search(i,j,k,I/2-k);
                }
            }
        }
 
        System.out.println(count);
 
 
 
 
 
    }
 
 
 
 
}

이 문제는 진짜 너무 어려워서 답지를 보면서도 고민을 오래했다.

물고기 2개를 선택해주고 그물의 길이도 선택해준다음에 search를 돌리면 된다. 

이렇게 노란색 칸과 초록색칸의 교집합에 있는 물고기의 개수를 세주면 된다.

결국 물고기가 그물망의 모서리에 걸쳐있게 그물을 내주면 된다.

이런식으로 구해주면 물고기가 그물의 꼭짓점에 있을 때는 물론 그물에 걸쳐있을때도 count 해줄 수 있다.

 

참고자료

https://justicehui.github.io/koi/2018/09/09/BOJ7573/

백준7573 고기잡이