백준 31965 (회의 장소) - java

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

 

문제

 

KOI 마을에는 N개의 집이 수직선 위에 지어져 있다. 각 집에는 사람들이 한 명씩 살고 있다. 사람들이 살고 있는 집의 좌표를 작은 순서대로 차례대로 나열했을 때, i (1≤i≤N)번째 집의 좌표는 Xi (Xi>0)이다. 마을에 일이 생기면, 마을 사람들은 회의 세트를 통해서 일을 해결한다. 회의 세트는 마을 사람들 전체가 참여할 수도 있고, 일부만 참여할 수도 있다. 회의 세트는 회의들로 구성된다. 회의는 회의 세트의 모든 참여자들이 그중 한 사람의 집에서 모이는 방식으로 진행된다. 회의 세트에서는 모든 참여자들의 집에서 각각 한 번씩 회의를 한다. 즉, 회의 세트에 K명의 마을 사람들이 참여한다면, 회의 세트에서는 K번의 회의를 하게 된다. 회의 한 번에 필요한 비용은 회의에 참여하는 각 사람이 자신의 집에서 회의 장소인 집까지 이동하는 거리의 합이다. 회의 세트의 피로도는 각 회의를 할 때 모이는 집의 순서에 따라 달라진다. 회의 세트의 피로도는 모이는 순서에서 인접한 두 집의 회의 비용 차이의 합으로 정의한다.

예를 들어, 좌표 1, 3, 10, 11, 15에 지어진 집에 사람들이 살고 있고, 3, 10, 11번 집에 사는 사람들이 회의 세트에 참여한다고 하자. 이때, 좌표가 3인 집에 모이기 위한 비용은 |3−3|+|3−10|+|3−11|=15이고, 좌표가 10인 집에 모이기 위한 비용은 |10−3|+|10−10|+|10−11|=8, 좌표가 11인 집에 모이기 위한 비용은 |11−3|+|11−10|+|11−11|=9이다. 이때, 회의를 위해 모이는 집의 좌표 순서가 3−10−11일 경우, 회의 세트의 피로도는 |15−8|+|8−9|=8이다. 반면, 모이는 집의 좌표 순서가 3−11−10일 경우, 피로도는 |15−9|+|9−8|=7이다. 이 순서로 모일 때, 회의 세트의 피로도가 최소이다.

단, 회의 세트에 참여하는 사람이 1명 이하일 경우, 0이 피로도이다.

KOI 마을에서는 총 Q번 회의 세트가 열릴 것이다. i번째 회의 세트는 집의 좌표가 L이상 R이하인 집에 사는 사람들이 참여한다. 각 회의 세트의 최소 피로도를 구하는 프로그램을 작성하라.

 

유형 : 이진 탐색 + 누적합

 

접근 방식

• 우선 L 이상 R 이하 구간을 선형적으로 구하면 시간 초과가 날 것 같다. 이진 탐색의 upper bound(L), lower bound(R)을 통해 구하면 될 것 같다.
• 피로도 계산은 다음과 같다.
  • 결국 최소값으로 모든 지점을 방문한다는 것은 피로도 순으로 정렬 했을 때 최대 - 최소이다.
    • 최대 지점은 양 쪽 끝 값 중 최댓값이다.
    • 최솟 값은 중간 지점의 값이다.
  • 피로도 수식은 누적합을 응용해야 한다. 방식은 고정값(중간 지점, 왼쪽 끝값, 오른쪽 끝값)을 기점으로 각 지점들의 차를 풀어서 보자

코드

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

public class BOJ_31965_회의_장소 {

    static int n,q;
    static long[] sum;
    static long[] num;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        n = Integer.parseInt(st.nextToken());
        q = Integer.parseInt(st.nextToken());

        num = new long[n + 1];
        sum = new long[n + 1];

        st = new StringTokenizer(br.readLine()," ");
        for (int i = 1; i <= n; i++) {
            num[i] = Long.parseLong(st.nextToken());
            sum[i] = sum[i-1] + num[i];
        }

        StringBuilder sb = new StringBuilder();

        for(int i = 1 ; i <= q ; i++) {
            st = new StringTokenizer(br.readLine()," ");

            int l = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());

            int lIdx = upper(l);
            int rIdx = lower(r);

            if(lIdx >= rIdx) {
                sb.append("0\n");
                continue;
            }

            long tmp1 = getValue(lIdx,lIdx,rIdx);
            long tmp2 = getValue(rIdx,lIdx,rIdx);
            long tmp3 = getValue((lIdx + rIdx) /2 , lIdx, rIdx);

            sb.append(Math.max(tmp1,tmp2) - tmp3).append("\n");
        }

        System.out.println(sb);

        br.close();
    }

    static long getValue(int t,int l,int r) {
        long rV = (sum[r] - sum[t - 1]) - (num[t] * (r - t + 1));
        long lV = (num[t] * (t - l + 1)) - (sum[t] - sum[l - 1]);

        return lV + rV;
    }


    static int upper(int target) {
        int l = 1;
        int r = n;

        while(l <= r) {
            int mid = (l + r) / 2;

            if(num[mid] >= target) {
                r = mid - 1;
            }else {
                l = mid + 1;
            }
        }

        return l;
    }

    static int lower(int target) {
        int l = 1;
        int r = n;

        while(l <= r) {
            int mid = (l + r) / 2;

            if(num[mid] > target) {
                r = mid - 1;
            }else {
                l = mid + 1;
            }
        }
        return r;
    }
}