[백준] 2141 우체국- 그리디 + 수학(median, 중간값) JAVA

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

2141번: 우체국

코드

그리디와 수학(중간값) 에 대한 문제입니다.

 

문제예시

3
1 3
2 5
3 3

위의 문제와 같이 예시가 있습니다.

첫번쨰 마을에 3명, 두번째 마을에 5명, 세번쨰 마을에 3명입니다.

여기서 중간값은 ( ( 3 + 5 + 3) + 1  )/ 2 = 6명, 여기서 중간값은 6명입니다.

6명보다 사람의 합이 커지거나 같으면 해당 마을의 위치가 최적의 장소가 됩니다.

만약 총 12명이 있을때, 왼쪽에 3명, 오른쪽에 3명이 되는 상황이 됩니다.

평균값이 아닌 중간값(median) 값을 구하기 위해서는 (n + 1) / 2 로 진행해야합니다.

 

여기서 의문점은, 마을의 위치와 중간값의 위치를 고려하지 않아도 괜찮은건가 라는 의문이 생기는데, 해당 의문이 아직 속시원하게 풀리지는 않았습니다. 단순히, 왼쪽 사람과 오른쪽 사람의 인구수가 최소한 으로 한다고하더라도, 마을의 위치와 비교하여 거리를 측정해야할 필요가 있어보이는데, 조금 더 생각이 필요합니다.

 

 

만약 위의 접근이 아닌, 첫번째 마을에 우체국을 세웠을때, 두번째마을과 세번쨰 마을에서 오는데 걸리는 비용

두번째 마을에 우체국을 세웠을때, 첫번째마을과 세번쨰 마을에서 오는데 걸리는 비용 이런식으로 계산하여 최소값을 구할 수도 있는데, 이럴 경우 시간초과가 발생합니다.

코드설명

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
	
	public static int N;
	public static long peopleSum = 0;
	public static Node[] node;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	node = new Node[N];
    	
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		long villagePos = Long.parseLong(st.nextToken());
    		long people = Long.parseLong(st.nextToken());
    		node[i] = new Node(villagePos, people);
    		peopleSum += people; // 전체 인원
    	}
    	
    	Arrays.sort(node); //마을 위치 기준 오름차순으로 정렬
    	
    	//가장 먼저 중간값보다 크거나 같은
    	long compareSum = 0;
    	for(int i=0;i<N;i++) {
    		compareSum += node[i].people;
    		if( ( (peopleSum + 1) / 2 <= compareSum )) { //중간값(median) 값보다 클 경우 해당 마을위치 출력
    			System.out.println(node[i].villagePos);
    			break;
    		}
    	}
    	
    }
}

class Node implements Comparable<Node>{
	long villagePos;
	long people;
	public Node(long villagePos, long people) {
		this.villagePos = villagePos;
		this.people = people;
	}
	
	@Override
	public int compareTo(Node other) {
		return (int) (this.villagePos - other.villagePos);
	}
}