백준 - 2513

import java.io.*;
import java.util.*;

class Apt implements Comparable<Apt>{
    int dist;
    int muns;

    public Apt(int dist, int nums){
        this.dist = dist;
        this.muns = nums;
    }
    @Override
    public int compareTo(Apt oth){
        return oth.dist - this.dist;
    }
}
public class Main {
    static int K;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 단지 수
        K = Integer.parseInt(st.nextToken()); // 버스 정원
        int S = Integer.parseInt(st.nextToken()); // 학교 타겟

        List<Apt> plus = new ArrayList<>();
        List<Apt> minus = new ArrayList<>();
        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            int dis = Integer.parseInt(st.nextToken());
            if (S - dis > 0) plus.add(new Apt(S-dis,Integer.parseInt(st.nextToken())));
            else minus.add(new Apt(dis-S,Integer.parseInt(st.nextToken())));
        }
        Collections.sort(plus);
        Collections.sort(minus);

        int answer = calc(plus) + calc(minus);
        System.out.println(answer);
    }
    static int calc(List<Apt> list){
        int res = 0;
        int cnt = 0;
        for(Apt a : list){
            cnt += a.muns;
            while(cnt > 0){
                res += a.dist * 2;
                cnt -= K;
            }
        }
        return res;
    }
}

풀이과정 및 리뷰

• 문제 접근:
  • 학교(S)를 기준으로 좌표가 왼쪽(plus), 오른쪽(minus) 으로 나뉘므로 각각 별도 관리
  • 버스는 한 번에 K명까지 태울 수 있으므로, 멀리 있는 아파트 단지부터 학생을 수송하는 것이 최적
  • 학생 수가 버스 정원을 넘으면 여러 번 왕복해야 하고, 남은 인원이 있으면 가까운 단지 학생들과 합쳐서 태우기 가능 → 그 단지는 별도의 왕복 비용이 발생하지 않음
    
• 시간복잡도: $O(N log N)$
• 풀이과정
  • 단지 정보를 dist(학교와의 거리) 기준 내림차순 정렬(이때 Plus, Minus 2개 리스트 생성해 별도관리)
  • cnt 변수를 이용해 아직 등교시키지 못한 학생 수 누적
  • 각 단지를 돌면서 cnt에 해당 단지 학생 수를 더하고, cnt > 0인 동안 버스 정원 K만큼 빼면서 왕복 거리를 추가
• 개선점 정렬 comparator

  Collections.sort(list, (a,b) -> b.dist - a.dist);

  로 람다식 사용하면 더 직관적 메모리 절약 plus, minus 나눠서 저장하지 않고, 입력 시 좌표 비교 후 바로 두 리스트에 add하면 충분