최소 국경

문제 

국경을 지나는 것은 언제나 귀찮고 힘든 일입니다. 여행자들은 도착지에 도착하기 위해 통과하는 국경을 최소화 시키길 원합니다. 당신은 여행자들을 도와 국경선을 최소한으로 통과하는 방법을 찾고 싶습니다. 다행히 당신이 도와줘야 하는 여행자가 사는 세상은 모든 나라의 국경선이 정확한 원이고 서로 겹치거나 교차하지 않는다고 합니다.

각 국가의 좌표 배열 X, Y 와 반지름 배열 R 그리고 시작 좌표인 x1, y1 종료 지점 좌표인 x2, y2가 주어진다고 할 때 최소한으로 통과해야 하는 국경선의 수를 리턴하는 함수를 작성하십시오.

입출력 예시

입력 1)

        int[] X = { 0, -6, 6 };

        int[] Y = { 0, 1, 2 };

        int[] R = { 2, 2, 2 };

        int x1 = -5;

        int y1 = 1;

        int x2 = 5;

        int y2 = 1;

출력 1)

  2

입력 2)

        int[] X = { 1, -3, 2, 5, -4, 12, 12 };

        int[] Y = { 1, -1, 2, 5, 5, 1, 1 };

        int[] R = { 8, 1, 2, 1, 1, 1, 2 };

        int x1 = -5;

        int y1 = 1;

        int x2 = 12;

        int y2 = 1;

출력 2)

  3

풀이

처음 문제를 읽으면 도대체 어떻게 풀어야 할지 감이 잡히지 않지만 시작 좌표와 종료 좌표가 속해있는 국경만 통과하면 된다는 사실을 생각할 수 있으면 의외로 간단한 문제이다. 

결국 각 좌표가 속해있는 국경의 수를 카운트 해서 반환하면 된다. 

코드

public int leastBorders(int[] X, int[] Y, int[] R, int x1, int y1, int x2, int y2) {
 
    int ret = 0;
    for (int i = 0; i < X.length; i++) {
        if ((X[i] - x1) * (X[i] - x1) + (Y[i] - y1) * (Y[i] - y1) < R[i] * R[i]
                && (X[i] - x2) * (X[i] - x2) + (Y[i] - y2) * (Y[i] - y2) > R[i] * R[i]
                || (X[i] - x1) * (X[i] - x1) + (Y[i] - y1) * (Y[i] - y1) > R[i] * R[i]
                        && (X[i] - x2) * (X[i] - x2) + (Y[i] - y2) * (Y[i] - y2) < R[i] * R[i]) {
            ret++;
        }
    }
 
    return ret;
}