BOJ18310 안테나(R)

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

18310번: 안테나

 

 

안테나를 왼쪽부터 오른쪽으로 이동한다고 생각하면 처음에는 계속 거리의 합이 작아 질것이다. 이렇게 작아지는 것이 만약 집이 5개라면 3번째지점을 지나는 순간에 다시 합이 커질 것이다. 왜냐하면 3번째집을 만나기전에는 2개에 집에서 한칸씩 멀어지더라도 3개의 집에서는 한칸씩 가까워 지기에 이득이였기 때문이다.

만약 집이 짝수라면 2번쨰집을 지나고 3번째집을 도착할 때까지는 값이 같기에 2번째집의 위치가 답이다.

중앙값의 성질을 이용한 문제이다.

이번에는 힌트를 보고 풀었으니 다시 풀어봐야겠다. 

 

import java.io.*;
import java.util.*;
public class Main
{
	public static void main(String[] args) throws IOException{
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    
	    int n = Integer.valueOf(br.readLine());
	    
	    
	    

        String[] input = br.readLine().split(" ");
        
        Integer[] points = new Integer[n];
        
        for(int i=0; i<n;i++){
            points[i] = Integer.valueOf(input[i]);
        }
        
        
        Arrays.sort(points);
        

	    int mid=0;
	    if(n%2==0){
	        mid+= Integer.valueOf(points[n/2-1]);
	    }else{
	        mid= Integer.valueOf(points[n/2]);
	    }
	    
        System.out.println(mid);
	    
	}
}