18310번 : 안테나

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

18310번: 안테나

 

 

문제

 

 

코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); sc.nextLine();
        String s[] = sc.nextLine().split(" ");
        Integer home[] = new Integer[n];
        
        for(int i=0;i<n;i++) {
            home[i] = Integer.parseInt(s[i]);
        }
        Arrays.sort(home);
        
        int index;
        if(n%2==0) {
            index = n/2-1;
        }else {
            index = n/2;
        }

        System.out.println(home[index]);

    }
}

 

 

해결방법

정답률이 34%길래 풀기 전에 좀 쫄았는데 풀고 나니 왜 34%인지 모르겠다.

집의 위치가 주어졌을 때 안테나로부터 모든 집까지의 거리의 총 합이 최소가 되려면 집 위치의 중간에 안테나를 설치하면 된다. 어찌 보면 당연한 것이긴 하다. 고로 집들의 위치를 정렬해서 중간인 집 위치를 출력해주면 되는데 집의 개수가 짝수개인 경우는 정확히 집의 중간이 없으므로 중간 위치에 있는 집 2개 중 더 작은 위치를 가진 집을 출력해주면 문제는 해결된다. 왜냐하면 중간 위치에 있는 집 2개는 안테나 설치 시 총 합의 값이 같기 때문이다.