백준 2141번 :: 우체국

최근엔 그리디 알고리즘을 풀고 있다. 개인적으로 제일 어렵다고 생각함..

각 문제마다 풀이를 접근했을 때 이게 어떻게 최적해가 보장이 되는 것인지 설명하기 어려워서 접근법을 구상해내는게 쉽지않음.. ㅠ 그런 문제 중 하나가 이번 '우체국' 문제라고 생각한데이...🥲

 

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

2141번: 우체국

 

접근방법

1. 그리디 알고리즘은 '정렬'이 핵심이라고 생각해서 우선 마을을 위치 기준으로 오름차순 정렬해줌

2. '각 사람들의 거리의 합이 최소가 되어야 한다' / '각 마을까지의 거리의 합이 아니라 각 사람까지의 거리의 합이다'

    여기서 말하는 거리라는 것은 "우체국 - 사람" 사이의 거리

    예를 들어, 2번 마을에 있더라도 해당 마을에 있는 사람들간의 거리는 또 다르다는 것.

    이 거리의 합이 최소가 되려면 우체국은 최대한 가운데에 위치하는 것이 최적해가 될 것

 

마을에 있는 인원수대로 사람에게 넘버링하면 이렇게 됨

    (편의상 번호대로 이름붙임) 6번이 있는 곳에 우체국을 지으면 순서대로

    ' 5 4 3 2 1 0 1 2 3 4 5 ' 만큼의 차이가 생기니까 총 30 거리만큼 차이가 남 (최소 거리)

    근데 만약에 우체국이 뭐,,, 1번이 있는 곳에 지었다고 해보면

    ' 0 1 2 3 4 5 6 7 8 9 10 ' 만큼의 차이가 생기므로 총 55 거리만큼 차이가 남

3. 그래서 인구 수를 순서대로 계산해서 중간 값과 가장 근접한 마을을 찾으면 됨

    인구 수를 하나씩 더한 값이 총 인원의 중앙값보다 크거나 같은 마을을 선택해줌  

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

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());
        List<Town> townList = new ArrayList<>(N);
        long totalPerson = 0;
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            long x = Integer.parseInt(st.nextToken());
            long a = Integer.parseInt(st.nextToken());
            townList.add(new Town(x, a));
            totalPerson += a;
        }

        Collections.sort(townList);

        long rs = 0;
        for (int i = 0; i < N; i++) {
            rs += townList.get(i).person;
            if ((totalPerson + 1) / 2 <= rs) {
                System.out.println(townList.get(i).x);
                break;
            }
        }
    }

    static class Town implements Comparable<Town> {
        long x;
        long person;

        public Town(long x, long person) {
            this.x = x;
            this.person = person;
        }

        // 마을 위치 기준 오름차순
        @Override
        public int compareTo(Town o) {
            if (this.x == o.x) return (int) (this.person - o.person);
            return (int) (this.x - o.x);
        }
    }
}

 

그리디 알고리즘 너무 어렵다 😭