[BOJ]8983번 : 사냥꾼

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

8983번: 사냥꾼

 

분류 : 라인 스위핑

 

import java.io.*;
import java.util.*;

public class Main {
    static Myscanner sc = new Myscanner();
    static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
    public static void main(String[] args) {
        int M = sc.nextInt();
        int N = sc.nextInt();
        int L = sc.nextInt();
        int[] shoot = new int[M];
        ArrayList<Point> animal = new ArrayList<>();
        for(int i=0;i<M;i++)
        {
            shoot[i] = sc.nextInt();
        }
        for(int i=0;i<N;i++)
        {
            int x = sc.nextInt();
            int y = sc.nextInt();
            animal.add(new Point(x,y));
        }
        Collections.sort(animal);
        Arrays.sort(shoot);
        int count =0;
        int cp = 0;
        for(int i=0;i<N;i++) //오름차순 정렬된 동물 X좌표
        {
            int tx = animal.get(i).x; //Target X
            int ty = animal.get(i).y; //Target Y
            if(ty<=L)
            {
                for(int j=cp;j<M;j++) //오름차순 정렬된 사대 X좌표
                {
                    if(inRange(shoot[j],tx,ty,L)){
                        count++;
                        cp = j; //현재 사대의 index 저장
                        break;
                    }
                    if(tx<shoot[j]) //동물 보다 x좌표값이 큰 사대 -> 못잡으면 이후에는 볼 필요 없음
                        break;
                }
            }
        }
        out.println(count);
        out.flush();
    }
    private static boolean inRange(int shoot, int tx, int ty, int l) {
        int dist = Math.abs(shoot-tx)+ty;
        
        if(dist<=l){
            return true;
        }
        else
            return false;
    }        
}
class Point implements Comparable<Point>{
    int x,y;
    Point(int x, int y){
        this.x = x;
        this.y = y;
    }
    @Override
    public int compareTo(Point p) {
        return this.x <= p.x ? -1: 1;
    }
    
}
class Myscanner {
    BufferedReader br;
    StringTokenizer st;

    Myscanner() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    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;
    }
}

 

한국 정보 올림피아드 KOI 2013 중등부 1번 문제이자 고등부 1번 문제이다.

입력이 무려 사대 = 100,000 동물의 수가 100,000이라 단순히 for문을 돌려서 확인하다가는

100억 번의 연산을 돌릴수 있다. (채점 프로그램아 힘내 ㅠㅠ)

그걸 방지 하기 위해서 몇 가지 장치를 구현하였는데,  첫번째는 동물 위치의 Y 좌표가 L보다 클 경우

동물과 사대의 거리는 | X-A|+B > L 이므로 이미 잡을 수 있는 사대는 존재 하지 않기 때문에 거른다.

 

 두번째로는 사대의 위치와 동물의 위치를 X좌표 기준으로 오름차순 정렬하였기 때문에,

만약 현재 사대의 위치와 인접한 동물 (Z라고 칭하자)을 잡지 못할 경우 

사대의 위치는 점점 더 멀어지기 때문에 Z를 잡을 가능성은 없다고 판단하여

Z의 x 위치보다 사대의 위치가 크다면 break를 걸어주었다.