https://www.acmicpc.net/problem/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를 걸어주었다.
'PS' 카테고리의 다른 글
[BOJ]1660번 : 캡틴 이다솜 (0) | 2017.04.26 |
---|---|
[BOJ]5052번 : 전화번호 목록 (0) | 2017.04.24 |
[BOJ]2352번 : 반도체 설계 (0) | 2017.04.20 |
[BOJ]1890번 : 점프 (0) | 2017.04.20 |
[BOJ]1620번: 나는야 포켓몬 마스터 이다솜 (0) | 2017.04.19 |