백준(BOJ) 11662 : 민호와 강호 (JAVA)

문제링크 : https://www.acmicpc.net/problem/11662

11662번: 민호와 강호

민호가 A -> B로, 강호가 C -> D로 걸어가는데 둘이 도착하는 시간이 같다. 이 때 민호와 강호가 가장 가까울 때의 거리를 구하는 문제이다. 별로 어려운 문제는 아니다. 민호가 가는 거리와 강호가 가는 거리를 일정 간격(interval)로 쪼개준 다음에 조금씩 이동시키면서 매번 거리를 구한 후 그 중에 가장 작은 값을 구하면 된다. 코드는 아래와 같다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        double aX1 = Double.parseDouble(st.nextToken());
        double aY1 = Double.parseDouble(st.nextToken());
        double aX2 = Double.parseDouble(st.nextToken());
        double aY2 = Double.parseDouble(st.nextToken());
        double cX1 = Double.parseDouble(st.nextToken());
        double cY1 = Double.parseDouble(st.nextToken());
        double cX2 = Double.parseDouble(st.nextToken());
        double cY2 = Double.parseDouble(st.nextToken());
        
        int interval = 1000000;
        
        double aDX = (aX2 - aX1) / interval;
        double aDY = (aY2 - aY1) / interval;
        double cDX = (cX2 - cX1) / interval;
        double cDY = (cY2 - cY1) / interval;
        
        double min = getDistance(aX1, aY1, cX1, cY1);
        
        for(int i = 1; i <= interval; i++) {
            double tmp = getDistance(aX1 + aDX * i, aY1 + aDY * i, cX1 + cDX * i, cY1 + cDY * i);
            
            if(tmp < min) {
                min = tmp;
            }
        }
        
        System.out.println(min);
    }
    
    private static double getDistance(double x1, double y1, double x2, double y2) {
        return Math.sqrt(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2));
    }
}

 

문제를 맞추고 난 후, 여느때와 다름없이 상위권 풀이와 비교해보니 어째 시간이 좀 길게 나오기도 하고, 푸는 방법도 달랐다. 구글링을 좀 해보니 '삼분탐색'이라고 하더라. 삼분탐색에 대한 자세한 설명은 아래 링크를 참고하면 좋다.

https://m.blog.naver.com/PostView.nhn?blogId=kks227&logNo=221432986308&proxyReferer=https%3A%2F%2Fwww.google.com%2F

삼분 탐색(Ternary Search)

근데 삼분탐색은, 최솟값을 구하는 경우 그 함수(여기선 i를 변수로 하는 함수라고 생각하면 된다)가 아래로 볼록할 때만 사용할 수 있다고 하더라. 근데 이게 아래로 볼록한 함수인지 어떻게 확신할 수 있지? 나는 그냥 수학적으로 직접 증명해보기로 했다. 고등학교 때 배웠던 미분이 약간 필요하다. 수학이라면 진절머리가 나는 사람이라면 그냥 스킵해도 좋다.

 

깔끔한 글씨로 계산해보려 했으나 실패...

일단 수학 시간이 아니므로 간단하게만 설명하겠다. f'(i) 의 분모는 항상 양수일 것이다.

분자는 (B^2 + D^2) * i + AB + CD인데, i의 계수는 항상 양수인 일차함수이므로 이 함수는 f'(i) 값이 음수에서 양수로 바뀌는, 즉 감소함수에서 증가함수로 바뀌는 함수라는 것을 알 수 있다. 아래로 볼록이라는 뜻이다. '이 문제에서 i는 0보다 크거나 개발자가 정한 최대값(interval)보다 작은 정수인데, 극소값이 존재하는 범위가 이 범위 밖에 벗어나면 그냥 증가함수나 감소함수가 되는 거 아닌가?!'라고 할 수도 있으나 삼분탐색은 그런 경우에도 사용 가능하다. 이분탐색보다 넓은 범위에서 사용 가능하다고 생각하면 될 것 같다. B^2 + D^2 = 0인 경우도 증가 혹은 감소함수가 될테니 설명 가능하다. (물론 AB+CD=0일 경우, 상수함수가 될텐데 이 경우에도 삼분탐색이 가능하긴 하다. 자세한 설명은 생략) 

 

이렇게 아래로 볼록이라는 걸 확실히 알 수 있을 때 삼분탐색을 이용해야하는 거 아닐까? 근데 생각해보자. 저렇게까지 계산했는데 굳이 삼분탐색을 이용해야할까?; 이왕 미분한거 극값이 나오는 i를 구해버리면 되지 않는가?!? 그래서 위의 계산식에 보면, f'(i) = 0일 때의 i값을 계산해놓았다. 분모가 0일때는 NaN이고, i가 범위를 벗어나는 경우도 있을 것이다. 그 경우에는 최소 값이 그래프의 양 끝 값 중 하나일 수밖에 없다. 

 

삼분탐색으로 푼 코드는 아래와 같다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        double aX = Double.parseDouble(st.nextToken());
        double aY = Double.parseDouble(st.nextToken());
        double bX = Double.parseDouble(st.nextToken());
        double bY = Double.parseDouble(st.nextToken());
        double cX = Double.parseDouble(st.nextToken());
        double cY = Double.parseDouble(st.nextToken());
        double dX = Double.parseDouble(st.nextToken());
        double dY = Double.parseDouble(st.nextToken());
        
        int interval = 1000000;
        
        double aDX = (bX - aX) / interval;
        double aDY = (bY - aY) / interval;
        double cDX = (dX - cX) / interval;
        double cDY = (dY - cY) / interval;
        
        int lo = 0;
        int hi = interval;
        
        while(hi - lo >= 3) {
            int p = (2 * lo + hi) / 3;
            int q = (lo + 2 * hi) / 3;
            
            double pVal = getDistance(aX + aDX * p, aY + aDY * p, cX + cDX * p, cY + cDY * p);
            double qVal = getDistance(aX + aDX * q, aY + aDY * q, cX + cDX * q, cY + cDY * q);
            
            if(pVal < qVal) {
                hi = q - 1;
            } else {
                lo = p + 1;
            }
        }
        
        double min = getDistance(aX + aDX * hi, aY + aDY * hi, cX + cDX * hi, cY + cDY * hi);
        
        for(int i = lo; i < hi; i++) {
            double temp = getDistance(aX + aDX * i, aY + aDY * i, cX + cDX * i, cY + cDY * i);
            
            if(temp < min) {
                min = temp;
            }
        }
        
        System.out.println(min);
    }
 
    private static double getDistance(double x1, double y1, double x2, double y2) {
        return Math.sqrt(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2));
    }
}

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        double aX1 = Double.parseDouble(st.nextToken());
        double aY1 = Double.parseDouble(st.nextToken());
        double aX2 = Double.parseDouble(st.nextToken());
        double aY2 = Double.parseDouble(st.nextToken());
        double cX1 = Double.parseDouble(st.nextToken());
        double cY1 = Double.parseDouble(st.nextToken());
        double cX2 = Double.parseDouble(st.nextToken());
        double cY2 = Double.parseDouble(st.nextToken());
        
        int interval = 1000000;
        
        double aDX = (aX2 - aX1) / interval;
        double aDY = (aY2 - aY1) / interval;
        double cDX = (cX2 - cX1) / interval;
        double cDY = (cY2 - cY1) / interval;
        
        double i = -1 * ((aX1 - cX1) * (aDX - cDX) + (aY1 - cY1) * (aDY - cDY)) / (Math.pow(aDX - cDX, 2) + Math.pow(aDY - cDY, 2));
        
        if(!Double.isNaN(i) && i < interval && i > 0) {
            double min = getDistance(aX1 + aDX * i, aY1 + aDY * i, cX1 + cDX * i, cY1 + cDY * i);
            System.out.println(min);
        } else {
            double min1 = getDistance(aX1, aY1, cX1, cY1);
            double min2 = getDistance(aX2, aY2, cX2, cY2);
            
            System.out.println(Math.min(min1, min2));
        }
    }
    
    private static double getDistance(double x1, double y1, double x2, double y2) {
        return Math.sqrt(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2));
    }
}

개인적으로 필자는 1번 풀이 혹은 3번 풀이가 좋은 풀이라고 본다. 즉, 이 문제를 굳이 삼분탐색으로 풀 이유가 없는 것 같다. 이유는, 아래로 볼록인 게 확실하지 않은 상황에서는 삼분탐색을 해선 안된다. 아래로 볼록인 걸 증명하기 위해 수학적 계산을 하면, 이 문제의 경우 미분 가능하기 때문에 그냥 극값을 구해버리는 게 낫다. 시간복잡도 측면에서 압도적으로 유리하기 때문이다. 필자가 남겨놓은 삼분탐색 참고를 위한 링크 글에서도 나오지만, 삼분탐색은 함수가 미분 불가능할 때만 써야할 것 같다.