[ boj : 14658 ] 하늘에서 별똥별이 빗발친다

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

14658번: 하늘에서 별똥별이 빗발친다

해설 : 그냥 정말 아무 생각하지 않고 문제만 바라봤을땐,,,,그냥 50만짜리 2차원 배열 선언해주고 길이가 L인 정사각형으로 한칸씩 밀면서 비교해주면 되겠네???싶을 것 입니다.

그러나 항상 우린 조건을 보고 생각을 해야겠죠?L이 최대 10만이고 50만x50만 이니 무조건 tle가 발생합니다.

다른 방법을 생각해보려고 했더니,,,,엥?별똥별의 개수가 100개 밖에 안되는 것을 발견했습니다. 그러면 굳이 2차원 배열을 선언해줘서 좌표들을 하나씩 기록하는 것이 아니라 그냥 k 만큼 계속 뺑뺑이 돌려주면서 비교해줘도 되네??라는 생각을 할 수 있는 것이죠.

이런 문제의 특징은 좌표가 주어지고 일정 범위내에 존재하는 '어떤 기록(여기서는 별똥별)' 의 개수를 찾으려고 할때 , 한 방향으로만 탐색해줘도 된다는 것 입니다.

즉, 상하좌우 전부 탐색해줄 필요가 없다는 말입니다. 그 이유는 만약 맨왼쪽 위부터 아랫방향으로 밀면서 탐색을 진행하게 된다면 왼쪽방향은 이미 그 전에 탐색이 진행됐기 때문입니다. 그러니 아직 탐색을 하지 않은 오른쪽 방향만 해줘도 충분하게 되는 것 입니다.

그리고 또한 별똥별의 개수들을 최대로 얻고 싶어하니 현재 별똥별이 경계선에 위치해 있을때가 가장 최적의 해가 됩니다. 별똥별이 (x,y) 좌표에 존재할때 x-l 부터 x+l 까지 의 범위만 체크하면 되는 것이죠.

이걸 알면 구현에서 실수만 하지 않고 조심히 잘 코드를 작성하면 됩니다.

이 블로그에 있는 '고기잡이' 문제와 사실상 똑같은 문제입니다.

//package com.boj.practice;
/*JAVA IO Template Reference : 류호석*/

import java.io.*;
import java.security.KeyPair;
import java.util.*;
import java.util.stream.Collector;
import java.util.stream.Collectors;

public class Main {
    private static FastIO scan = new FastIO();

    static int n,m,l,k;

    public static void main(String[] args) throws IOException{
        //int t;
        //t = scan.nextInt();
        //while(t-->0){
        solve();
        //}
    }
    public static void solve() throws IOException{
        List<Pair> v = new ArrayList<>();
        n = scan.nextInt();
        m = scan.nextInt();
        l = scan.nextInt();
        k = scan.nextInt();

        int x,y;
        for(int i=0;i<k;i++){
            x = scan.nextInt();
            y = scan.nextInt();
            v.add(new Pair(x,y));
        }
        int ans=0;
        for(int p=0;p<k;p++){
            for(int i=v.get(p).x-l,j=v.get(p).y;i<=v.get(p).x;i++){
                if(i<0 || i+l>500_000 || j+l>500_000)continue;
                int cnt=0;
                for(int q=0;q<v.size();q++){
                    if(i<=v.get(q).x && v.get(q).x<=i+l && j<=v.get(q).y && v.get(q).y<=j+l)
                        cnt++;
                }
                ans = Math.max(ans,cnt);
            }
        }
        System.out.println(k-ans);
    }
}
class Pair{
    int x,y;

    public Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
class FastIO{
    BufferedReader br;
    BufferedWriter bw;
    StringTokenizer st;

    public FastIO(){
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
    }
    void write(String str) throws IOException{
        bw.write(str);
    }
    void flush() throws IOException{
        bw.flush();
    }
    int nextInt(){
        return Integer.parseInt(next());
    }
    double nextDouble(){
        return Double.parseDouble(next());
    }
    Long nextLong(){
        return Long.parseLong(next());
    }
    String nextLine(){
        String str="";
        try{
            str = br.readLine();
        }catch (IOException e){
            e.printStackTrace();
        }
        return str;
    }
    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }
}