백준 18310 - 안테나 (자바 - 그리디)

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

18310번: 안테나

 

* 문제 요약

일직선 상의 마을에 여러 채의 집이 위치해 있다. 이 중에서 특정 위치의 집에 특별히 한 개의 안테나를 설치하기로 결정했다.

효율성을 위해 안테나로부터 모든 집까지의 거리의 총 합이 최소가 되도록 설치하려고 한다.

이 때, 안테나는 집이 위치한 곳에만 설치할 수 있고, 논리적으로 동일한 위치에 여러 개의 집이 존재하는 것이 가능하다.

집들의 위치 값이 주어질 때, 안테나를 설치할 위치를 선택하는 프로그램을 작성하시오.

 

예를 들어 N = 4 이고, 각 위치가 1,5,7,9 일 때를 가정하자.

이 경우 5의 위치에 설치했을 때, 안테나로부터 모든 집 까지의 거리의 총 합이 4+0+2+4 = 10 으로 최소가 된다.

 

* 입력

첫째 줄에 집의 수 N 이 자연수로 주어진다. (1 <= N <= 200,000)

둘째 줄에 N 채의 집의 위치가 공백을 기준으로 구분되어 1 이상 100,000 이하의 자연수로 주어진다.

 

* 출력

첫째 줄에 안테나를 설치할 위치의 값을 출력한다. 단, 안테나를 설치할 수 있는 위치의 값으로 여러개의 값이 도출될 경우 가장 작은 값을 출력한다.

 

* 예시

 

* 해결 과정

집의 숫자 N 의 최대값이 200,000 인 시점에서 이중반복으로 각 집 마다 안테나를 설치해서 다른 집과의 거리를 모두 계산 한 뒤, 그 중에서 최솟값을 찾는식으로 문제를 푼다면 반드시 시간 초과라는 결과를 얻게 되리라는 것을 직감했다.

이걸 어떻게 풀어야 하나 고민하다, 설마 집 들 중에서 정중앙에 위치한 집에 안테나를 설치해야 하나는 생각에 닿았을 때 질문게시판에서 아래와 같은 글을 찾았다.

맨 왼쪽 집에서부터 차를 타고 오른쪽으로 간다고 생각해봅시다. 이 때 모든 집까지의 거리는 줄어들 것입니다. 
맨 왼쪽 집과만 멀어지기 때문이죠
계속 가다보니 모든 집과의 거리가 갑자기 늘어나기 시작하는 때가 있습니다. 내 오른쪽에 있는 집 보다 내 왼쪽에 있는 집이 더 많아져서 모든 집까지의 거리가 증가하기 때문입니다.
즉, 왼쪽부터 오른쪽으로 갈 때 모든 집 까지의 거리가 증가하는지, 감소하는지는 내 왼쪽의 집의 갯수가 더 많나, 내 오른쪽의 집의 갯수가 더 많나에 달렸습니다.
따라서 왼쪽 집의 갯수가 오른쪽 집의 갯수를 넘어서기 직전이 모든 집까지의 거리가 최솟값이 되는 지점입니다.
(함수로 따지면 기울기가 - 에서 + 로 변화가 생기는 지점)
이때 이것을 무조건 만족하는 지점이 중간값입니다. 중간값이면 왼쪽과 오른쪽에 있는 집의 갯수가 같게 되거나 같게 되는 구간의 왼쪽 끝이 되기 때문입니다.

 

위의 글을 보고 모든 집과의 거리가 계속 감소하면서 이내 그 감소치가 최대가 되는 지점이 (그때까지 지속적으로 모든 집과의 거리가 감소하므로) 바로 중간값 이라는 점을 깨달았고, 이는 위에서 생각했던 정중앙에 위치한 집에 안테나를 설치하면 모든 집과의 거리의 합이 최소가 되지 않을까라는 의문에 답을 주었다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().solution();
    }

    private void solution() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int count = Integer.parseInt(br.readLine());
        int[] antenna = new int[count];

        String[] input = br.readLine().split(" ");
        for (int i = 0; i < antenna.length; i++) {
            antenna[i] = Integer.parseInt(input[i]);
        }

        Arrays.sort(antenna);
        int index = 0;
        if (antenna.length % 2 == 0)
            index = (antenna.length / 2) - 1;
        else
            index = antenna.length / 2;

        bw.write(antenna[index] + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

 

그냥 정중앙에 위치한 집에 안테나를 설치하는게 모든 집과의 거리를 최소화 하는 방법이므로

현재 상태에서 최적의 해답 선택 -> 모든 집과의 거리가 최소가 되는 위치인 정중앙

선택된 해가 문제의 조건을 만족하는지 검사 -> 정말로 정중앙에 안테나를 설치하는게 모든 집과의 거리를 최소화 시킬 수 있는게 맞는지에 대한 증명

위의 2가지 근거를 통해 이 문제가 그리디 알고리즘 문제임을 알 수 있다.