[ boj : 7573 ] 고기잡이

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

7573번: 고기잡이

해설 : 단순히 생각했을때 2차원배열로 선언해서 접근할수도 있을 것 같지만 N의 범위가 1만이니 아마 메모리 초과가 발생할 것 입니다.

그런데 굳이 2차원 배열을 만들필요가 있을까요???그물의 길이도 100, 물고기의 최대 수도 100이니 그냥 주어진 입력값들만으로도 충분히 범위를 구할 수 있습니다.

즉, 모든 가능한 경우의 수를 직접 해보면 된다는 뜻입니다. 이때, 네방향(왼쪽 위, 오른쪽 위, 왼쪽 아래,오른쪽 아래) 를 모두 확인할 필요는 없습니다. 2가지 방향(오른쪽 위, 오른쪽 아래) 만 확인해도 충분합니다.

그 이유는 왼쪽 위와 왼쪽 아래는 어차피 그 전의 동작으로 인해서 확인이 될 것이기 때문입니다. 물고기가 경계선에 있어야지 최대한 이득을 많이 볼 수 있기 때문입니다.

import java.io.*;
import java.security.KeyPair;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
import static java.lang.Math.*;

public class Main {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        input();
    }

    static void input(){
        int n,I,m;
        n = scan.nextInt();
        I = scan.nextInt();
        m = scan.nextInt();
        int x,y;
        List<Pair> v = new ArrayList<>();

        for(int i=0;i<m;i++){
            x = scan.nextInt();
            y = scan.nextInt();
            v.add(new Pair(x,y));
        }
        int ans=0;
        for(int i=0;i<m;i++){
            for(int j=1;2*j<I;j++){
                int xlen=j,ylen=(I-(2*j))/2;
                for(int tx=v.get(i).x-xlen;tx<=v.get(i).x;tx++){
                    int cnt=0;
                    int ty = v.get(i).y;
                    if(tx<=0 || tx>n || ty<=0 || ty>n)continue;
                    //cnt=1;
                    for(int p=0;p<m;p++){
                        //if(i==p)continue;
                        if(tx<=v.get(p).x && v.get(p).x<=tx+xlen && ty<=v.get(p).y && v.get(p).y<=ty+ylen){
                            cnt++;
                        }
                    }
                    ans = max(ans,cnt);
                }
            }
        }
        System.out.println(ans);
    }

    static class Pair{
        int x,y;
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;
        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {

            return Integer.parseInt(next());

        }

        long nextLong() {

            return Long.parseLong(next());

        }

        double nextDouble() {
            return Double.parseDouble(next());
        }
        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}