[백준 31965번] 회의 장소

문제 링크

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

 

피로도를 최소로 하는 회의 순서 정하기

회의 세트에 참여하는 K개의 집의 좌표를 오름차순으로 \(x_1, x_2, \cdots, x_k\)라고 하고, 각 집에서 회의를 개최했을 때 드는 비용을 \(c_1, c_2, \cdots, c_k\)라고 정의하자.

 

각 집에서 회의를 개최했을 때 드는 비용을 계산한 뒤 유심히 관찰해 보면, 회의 비용이 감소하거나 증가하는 방향으로 회의를 개최할 때 피로도가 최소가 된다는 것을 발견할 수 있다. 그 이유는 회의 비용이 정렬되어 있으면 인접한 회의의 비용 차이를 최소화할 수 있기 때문이다.

 

회의 비용이 정렬되어 있을 때 피로도는 \(c_1, c_2, \cdots, c_k\)중에서 최댓값과 최솟값의 차이와 같고, 이때가 바로 만들 수 있는 최소의 피로도가 된다.

 

최대 회의 비용과 최소 회의 비용

회의 장소를 \(x_i\)에서 \(x_{i+1}\)로 옮길 때 비용이 얼마나 변하는지 계산해 보자. 비용 변화는 두 부분으로 나눠서 계산할 수 있다.

 

첫 번째 집부터 \(i\)번째 집까지는 이동 거리가 \((x_{i+1} - x_i)\)만큼 멀어지므로, 회의 비용은 \(i \times (x_{i+1} - x_i)\)만큼 증가한다. \(i+1\)번째 집부터 K번째 집까지는 이동 거리가 \((x_{i+1} - x_i)\)만큼 줄어드므로, 회의 비용은 \((k - i) \times (x_{i+1} - x_i)\)만큼 감소한다. 회의 비용의 총변화량은 증가량과 감소량의 합으로 계산할 수 있으며 아래와 같이 정리할 수 있다.

$$\displaylines{\begin{align} \triangle C& = i \times (x_{i+1} - x_i) - (k - i) \times (x_{i+1} - x_i) \\ & = (2 \times i - k) \times (x_{i+1} - x_i)\end{align}}$$

이를 통해, 회의 장소를 첫 번째 집부터 K번째 집으로 옮길 때의 비용 변화를 분석해 보자. 비용은 첫 번째 집에서 시작하여 점점 줄어들다가 \(\lfloor{\frac{k + 1}{2}}\rfloor\)번째 집에서 최소가 되었다가, 다시 증가하기 시작한다. 즉, 첫 번째 집 혹은 K번째 집에서 회의를 열 때 비용이 최대가 되고 \(\lfloor{\frac{k + 1}{2}}\rfloor\)번째 집에서 회의를 열 때 비용이 최소가 되는 것을 알 수 있다.

 

회의 비용 빠르게 계산하기

\(i\)번째 집에서 회의를 열었을 때 비용은 \(\sum_{j=1}^k |x_i - x_j|\)로 계산할 수 있다. 절댓값 기호를 없애기 위해서 \(i\)번째 집보다 작은 좌표에 있는 왼쪽 집들과 큰 좌표에 있는 오른쪽 집들로 나눠서 생각해 보자.

 

왼쪽 집들은 전부 좌표가 \(x_i\)보다 작으므로 \(\sum_{j=1}^i(x_i - x_j)\)으로 계산할 수 있고 \(i \times x_i - \sum_{j=1}^i x_j\)으로 정리할 수 있다. 오른쪽 집들은 전부 좌표가 \(x_i\)보다 크므로 \(\sum_{j=i}^k(x_j - x_i)\)으로 계산할 수 있고 \(\sum_{j=i}^k x_j - (k - i + 1) \times x_i\)으로 정리할 수 있다.

 

회의 세트에 포함된 집들은 전부 연속된 집들이기 때문에 Prefix Sum 알고리즘을 이용하면 회의 비용을 빠르게 계산할 수 있다.

 

회의 세트에 포함된 집들을 빠르게 찾기

이분 탐색을 사용하면 각 질의마다 주어진 \(L\)과 \(R\)에 포함되는 집들을 로그 시간 안에 빠르게 찾을 수 있다.

 

소스 코드

 

#include <stdio.h>
#include <algorithm>

using namespace std;

int n, q, l, r;
long long X[200010], P[200010];

/**
 * 특정 집에서 회의를 개최할 때의 비용을 계산하는 함수
 * @param i - 회의 세트에 포함된 집들의 시작 인덱스
 * @param j - 회의 세트에 포함된 집들의 끝 인덱스
 * @param k - 회의를 개최하는 집의 인덱스
 * @return - 집 k에서 모일 때의 총 비용
 */
long long getCost(int i, int j, int k) {
    long long leftCost = (long long)(k - i + 1) * X[k] - (P[k] - P[i - 1]);
    long long rightCost = (P[j] - P[k - 1]) - (long long)(j - k + 1) * X[k];
    
    return leftCost + rightCost;
}

int main() {
    // n: 집의 개수, q: 질의의 개수
    scanf("%d%d", &n, &q);
    
    // 집의 좌표와 누적 합 계산
    for (int i = 1 ; i <= n ; ++i) {
        scanf("%lld", &X[i]);
        P[i] = P[i - 1] + X[i];
    }
    
    // 각 질의에 대해 처리
    while (q--) {
        scanf("%d%d", &l, &r);
        // 주어진 범위 [l, r]에 해당하는 집의 인덱스 범위를 찾기 위해 이분 탐색 사용
        int lo = lower_bound(X + 1, X + n + 1, l) - X;
        int hi = upper_bound(X + 1, X + n + 1, r) - X - 1;
        
        // 범위 내에 집이 없을 경우
        if (lo >= hi) {
            puts("0");
        } else {
            // 최대 회의 비용과 최소 회의 비용 계산
            long long maxStress = max(getCost(lo, hi, lo), getCost(lo, hi, hi));
            long long minStress = getCost(lo, hi, (lo + hi) / 2);
            
            // 최소 피로도를 출력
            printf("%lld\n", maxStress - minStress);
        }
    }
}