순간을 성실히, 화려함보단 꾸준함을

[ boj : 7573 ] 고기잡이 본문

알고리즘,SQL/백준,BOJ

[ boj : 7573 ] 고기잡이

폭발토끼 2022. 1. 22. 01:01

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

 

7573번: 고기잡이

한국인의 식단에서 생선은 매우 중요한 단백질 공급원이다. 반면, 지구 온난화로 인한 바닷물의 온도 상승, 그리고 지금까지 마구잡이로 물고기를 잡은 결과로 점점 우리나라의 바다에서 물고

www.acmicpc.net

해설 : 단순히 생각했을때 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;
        }
    }
}

'알고리즘,SQL > 백준,BOJ' 카테고리의 다른 글

[ boj : 22868 ] 산책(small)  (0) 2022.01.26
[ boj : 22942 ] 데이터 체커  (0) 2022.01.22
[ boj : 1301 ] 비즈 공예  (0) 2022.01.17
[ boj : 22236 ] 가희와 비행기  (0) 2022.01.16
[ boj : 22234 ] 가희와 은행  (0) 2022.01.15