[백준 / BOJ] 1087 쥐 잡기

문제

출처 : https://www.acmicpc.net/problem/1087

1087번: 쥐 잡기

김지민은 쥐를 잡는 게임을 만들었다. 쥐는 각자의 시작위치(x,y)부터 1초마다 (dy,dx)방향으로 움직이며, 이때 속력은 항상같다.

 

쥐는 한변의 길이가 L인 x축에 평행인 정사각형 모양의 울타리로 쥐를 가둔다음, 판 밖으로 밀어내면 잡힌다.

(쥐가 울타리의 경계에 있다면 잡힌쥐가 아니다)

 

한번에 모든 쥐를 절대로 잡을 수 없는 가장 큰 L을 구하는 프로그램을 만드는 문제다.

 

풀이

삼분탐색으로 풀은 문제다.

 

가장 먼 쥐 뒤마리 사이의 거리가 최소가 되는 지점을 찾아 울타리를 찾아서 풀면 되는 문제다.

- 울타리의 크기는 가장 먼쥐 두마리 사이의 거리일것이기 때문이다.(쥐가 겹쳐있으면 울타리안에 들어가지 않는것이므로...)

쥐는 한 방향으로만 움직이므로, 가장 먼 쥐 두마리 사이의 거리가 최소가 되는지점이 언젠가 반드시 나타난다.

 

쥐의 위치는 -1000 ~ 1000 이므로 최악의 경우 약 4000번 탐색으로 최소가 되는 지점이 나타날거라 생각해서, 완전탐색으로 풀려했으나...

시간이 (1.111.... 초 1.2.... 초 1.343424 초 ...)등에서 최소가 되는 지점이 나타날수도 있으므로 완탐으로는 안풀리고 삼분탐색으로 극솟값을 찾아줘야했다.

 

쥐는 한 방향으로만 움직이므로, 가장 먼 쥐 두마리 사이의 거리가 최소가 되는지점이 언젠가 반드시 나타난다.

 

위 정의를 다시생각해보면, 

- 모든 쥐들은 한 방향으로만 이동하므로, 서로의 반대방향으로 이동하는 쥐의 길이는 항상 더 멀어지고, 반대로 서로의 가까워지는 쥐들은 일정한 시간동안은 가까워지다가 멀어지기 시작할것이다. 

따라서, 가장 먼 쥐 두마리 사이의 거리가 그리는 그래프는 극솟값을 갖는 2차원 그래프이며, 삼분탐색을 적용할수있는걸 알수있다.

 

삼분탐색을 이용해서, 가장 먼 쥐들의 거리가 가장 가까울때(극솟값)의 거리를 출력하면된다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1087%20%EC%A5%90%20%EC%9E%A1%EA%B8%B0/main.cpp

devxb/JJUNalgo