백준 2317번: 결혼식

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

2317번: 결혼식

결혼 축하 기차의 세 인접한 사람 혹은 사자의 키 H1, H2, H3에 대해, H1 < H2 < H3 혹은 H1 > H2 > H3이라면 세 키의 차이의 합은 H1 - H3의 절댓값과 같다. 따라서 사자의 키의 최솟값과 최댓값을 알고 있다면, 해당 범위 내에 있는 사람의 키는 결과값에 영향을 주지 못한다. 또, 사자의 키의 범위를 벗어나는 사람들을 키 순으로 정렬한 뒤 한 batch로 묶어 사자의 행렬에 추가하면 각 사람끼리의 키의 차이 역시 무시할 수 있다. 따라서 사람의 키 중 필요한 건 사자의 키를 벗어난 사람 중 최댓값과 최솟값 두 값이다.

인접한 사자끼리의 키 차이의 합을 이미 알고 있다고 가정하자. 사자의 키의 범위를 벗어난 키 H를 가진 사람이 결혼 축하 기차에 들어갈 수 있는 경우의 수는 열차의 시작, 열차의 끝, 혹은 열차의 중간이다.

열차의 중간에 들어가는 경우 인접한 두 사자의 키 L1, L2에 대해, 키 차이의 합은 총 |L1 - H| + |L2 + H|가 된다. 이 때 |N|은 N의 절댓값을 뜻한다. 이 값을 최소화하기 위해선 L1과 L2가 최대한 H에 가까워야 하는데, H가 사자의 키의 최댓값보다 큰 경우 이 값은 2 * |최댓값 - H| + |최댓값 옆의 키 - 최댓값|이고, 사자의 키의 최솟값보다 작은 경우 2 * |최솟값 - H| + |최솟값 옆의 키 - 최솟값|이다. 이 때 최댓값 혹은 최솟값과 그 옆의 키 차이는 이전에 구한 합이 가지고 있으므로, 결국 필요한 값은 2 * |최댓값 - H| 혹은 2 * |최솟값 - H|이다.

세 가지 경우에 발생하는 키의 차이를 계산한 뒤, 인접한 사자끼리의 키 차이의 합에 더한다면 정답을 구할 수 있다.

#include <cstdio>

#define MAX_K 1000
#define MIN(a, b) (a < b ? a : b)
#define MAX(a, b) (a > b ? a : b)

// N: 열차의 길이, K: 사자의 수
int N, K, lion[MAX_K];

int abs(int n) { return n < 0 ? -n : n; }

int check_leftover(int H, int L) {
    // 열차의 중간에 최댓값 혹은 최솟값을 넣을 경우
    int ret = abs(H - L) << 1;

    // 열차의 시작 혹은 끝에 최댓값 혹은 최솟값을 넣을 경우
    ret = MIN(ret, abs(lion[0] - H));
    ret = MIN(ret, abs(lion[K - 1] - H));

    // 세 경우를 비교한 뒤 가장 작은 값을 반환
    return ret;
}

int main () {
    // ans: 열차에서 인접한 키의 차이의 합
    // H[i]: 사람의 키의 {최솟값, 최댓값}[i]
    // L[i]: 사자의 키의 {최솟값, 최댓값}[i]
    // buf: 사람의 키를 임시로 입력받을 공간
    int ans = 0, H[2] = { 0, }, L[2] = { 0, }, buf;

    // 초기의 최솟값을 INT_MAX로, 초기의 최댓값을 0으로 초기화
    H[0] = L[0] = __INT_MAX__;

    // 열차의 길이와 사자의 수를 입력받은 뒤
    scanf("%d %d", &N, &K);

    // 사자의 키를 입력받아 그 범위를 계산
    for (int i = 0; i < K; i++) {
        scanf("%d", lion + i);
        L[0] = MIN(L[0], lion[i]);
        L[1] = MAX(L[1], lion[i]);
    }

    // 사람의 키를 입력받아 그 범위를 계산
    for (int i = K; i < N; i++) {
        scanf("%d", &buf);
        H[0] = MIN(H[0], buf);
        H[1] = MAX(H[1], buf);
    }

    // 인접한 사자끼리의 키의 차이의 합을 계산
    for (int i = 1; i < K; i++) ans += abs(lion[i] - lion[i - 1]);

    // 사람의 키의 최솟값과 최댓값이 사자의 키의 범위를 벗어난 경우
    // 사자의 배열에 사람의 키를 넣은 경우의
    // 차이의 최솟값을 계산해 ans에 더한다
    if (H[0] < L[0]) ans += check_leftover(H[0], L[0]);
    if (H[1] > L[1]) ans += check_leftover(H[1], L[1]);

    // 기차에서 인접한 앞뒤사람의 키 차이를 모두 더한 값을 출력
    printf("%d\n", ans);

    return 0;
}