[PS] BOJ18310 안테나 ( greedy ) with JAVA

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

18310번: 안테나

 

 

◎ 문제풀이

 

 

 

 

안테나를 어느 집에 설치해야 [ 안테나 - 집 ] 거리의 합이 최소가 되는 지를 묻는 문제이다. 집은 { 1 , 5 , 9 , 9 , 9 , 11 } 에 주어졌다고 가정하자. 안테나의 위치를 x라고 한다면,

 

sum = [ x - 1 ] + [ x - 5 ] + [ x - 9 ] + [ x - 9 ] + [ x - 9 ] + [ x - 11 ] 

sum의 최솟값을 구하는 문제이다. 

 

안테나가 양 끝에 있으면

안테나와의 거리의 합은 최대가 된다. 

 

그러므로

안테나는 최대한 중간에 위치해야 안테나와의 거리가 최소가 된다. 

 

n이 6이라면,

 

 

 

2번 인덱스는 (n-1)/2이다.

인덱스는 0부터 시작하므로 중간 인덱스는 n/2가 아닌 (n-1)/2이 된다.

 

그러나 짝수인 경우,

3번 인덱스, 즉  n/2도 중간이 될 수 있다.

 

이렇듯 n이 짝수이면 중간이 두 가지가 나온다. 

문제에서 여러 개가 도출되면 가장 작은 값을 출력하라고 했으므로, (n-1)/2가 정답이다.

 

 

 

 

n이 홀수이면 중간은 하나이다. 

그러므로 (n-1)/2가 정답이다. 

 

정리하면, 안테나와의 거리는 끝으로 가면 갈수록 최대가 되므로 최대한 집들의 중앙에 위치한 집에 설치해야 한다. 중앙을 찾기 위해, 먼저 오름차순으로 정렬을 하고 집의 개수를 고려해서 중앙 인덱스가 가리키는 집을 구하면 된다. 

 

 

이런 문제를 처음 접했다면 쉽지 않은 문제였다. 구현보다는 발상이 어려운 문제였다.

 

 

◎ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

//BOJ18310 안테나
public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[n];

        for(int i=0;i<n;i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr); // 오름차순 정렬
        System.out.println(arr[(n-1)/2]); // 중앙 인덱스가 가리키는 집 출력

    }

}