C++로 선분의 중심을 이동해 만들 수 있는 최대 교차 영역 구하기

이 튜토리얼에서는 선분들의 중심을 이동시켜 얻을 수 있는 최대 교차 영역을 구하는 프로그램을 다룹니다.

문제 조건은 다음과 같습니다. 길이가 모두 같은 세 선분의 중심 좌표와 선분의 길이 L, 그리고 각 중심을 이동할 수 있는 최대 거리 K가 주어집니다. 목표는 각 중심을 최대 K만큼씩 이동시켜 세 선분이 동시에 겹치는 구간, 즉 공통 교차 영역의 길이를 최대화하는 것입니다.

알고리즘 접근 방식

핵심 아이디어는 세 중심 좌표를 먼저 오름차순으로 정렬한 뒤, 가장 바깥쪽에 있는 두 중심 사이의 거리(center[2] − center[0])를 기준으로 경우를 나누어 판단하는 것입니다.

• 경우 1 — 교차 불가능: 바깥쪽 두 중심의 거리가 2K + L 이상이라면, 중심을 K만큼씩 이동해도 세 선분이 모두 겹칠 수 없으므로 교차 영역의 길이는 0입니다.
• 경우 2 — 부분적으로만 교차 가능: 그 거리가 2K 이상이라면, 양 끝 선분을 서로 향해 최대한 밀어붙였을 때 남는 교차 길이인 2K − (거리 − L)이 답이 됩니다.
• 경우 3 — 완전히 교차 가능: 그 외의 경우에는 중심들이 충분히 가까워 있어 이동하지 않아도 세 선분을 완전히 겹치게 만들 수 있으므로, 교차 영역의 최대 길이는 선분의 길이 L 그 자체입니다.

세 개의 원소만 정렬하면 되기 때문에 이 알고리즘은 사실상 상수 시간(O(1)) 안에 동작합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
// 최대 교차 영역의 길이 계산
int max_intersection(int* center, int length, int k) {
    sort(center, center + 3);
    if (center[2] - center[0] >= 2 * k + length) {
        return 0;
    }
    else if (center[2] - center[0] >= 2 * k) {
        return (2 * k - (center[2] - center[0] - length));
    }
    else
        return length;
}
int main() {
    int center[3] = { 1, 2, 3 };
    int L = 1;
    int K = 1;
    cout << max_intersection(center, L, K);
}

실행 결과

1

위 예제에서 세 선분의 중심은 {1, 2, 3}이고, 선분의 길이 L은 1, 이동 가능 거리 K는 1입니다. 바깥쪽 두 중심 사이의 거리는 2로, 이 값은 2K + L(= 3)보다는 작지만 2K(= 2) 이상이므로 두 번째 경우에 해당합니다. 따라서 2 × 1 − (2 − 1) = 1이 계산되어 교차 영역의 최대 길이인 1이 출력됩니다.