백준 2141 우체국

문제링크

https://www.acmicpc.net/submit/2141/42113933

문제

풀이

정렬+그리디

마을에 대해서가 아니라 각 마을에 존재하는 사람들에 대해 우체국이 최적의 위치에 있어야 한다는 점을 유의하자.
따라서 마을마다 가중치가 서로 다르다.
최적의 우체국 거리는 각 사람들마다 우체국과의 거리를 계산했을 때 그 합이 최소인 경우다.

이 문제를 풀기 위해 현재 위치를 기준으로 좌,우에 각각 인구가 몇명인지 파악하고 좌 우의 인구 차이에 따라 이동할때 마다 생기는 우체국과의 거리 합 변화를 파악해야 한다.

왼쪽에서 오른쪽으로 한 칸 이동하면 우체국 기준으로
왼쪽 인구 +1 , 오른쪽 인구 -1 만큼의 최적거리 변화가 생긴다. 따라서 오른쪽으로 더 이동하는게 손해가 되기 전까지 이동을 시켜주어야 한다.
여기서 오른쪽으로 더 이동하는게 손해가 되는 시점은 왼쪽 인구가 오른쪽 인구보다 많아지는 때부터 이다이다.

이 원리를 코드로 구현하기만 하면 문제를 해결할 수 있다.

코드

const input = require('fs').readFileSync('./dev/stdin').toString().trim().split('\n');

let n = +input[0];
let arr = [];

let people=0;
for(let i=1;i<input.length;i++){
    let [x,a] = input[i].split(' ').map(Number);
    //console.log(input[i].split(' ').map(Number))
    arr.push([x,a]);
    people+=a;
}

arr.sort((a,b)=>{
    if(a[0]>b[0]) return 1;
    return -1;
})

let left=0;
let right=people-arr[0][1];

let min = Math.abs(left+right);
let pos = arr[0][0];

for(let i=1;i<arr.length;i++){
    left+=arr[i-1][1];
    right -= arr[i][1];

    let temp = Math.abs(left+right);
    if(temp<min){
        min=temp;
        pos=arr[i][0];
    }
}

console.log(pos);

후기

풀이만 떠올리면 구현 자체는 어렵지 않은 문제였다.