C++ 배열에서 점 선택하기: 자석 간 최소 거리를 최대화하는 방법

문제 개요

이 문제에서는 N개의 인덱스 위치를 나타내는 n개의 요소로 구성된 배열 arr[]와 C개의 자석이 주어집니다. 우리의 목표는 가장 가까운 두 자석 사이의 거리가 최대한 크도록 모든 자석을 배치하고, 그때의 최소 거리 값을 구하는 것입니다.

예시를 통해 문제를 살펴보겠습니다.

입력 − array = { 1, 4, 6, 12, 28, 44 }, C = 4

출력 − 11

해결 접근 방법

이 문제는 이진 탐색(Binary Search)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

먼저 가능한 최대 거리를 하나 정한 뒤, 그 거리(mid) 이상의 간격을 유지하면서 0부터 최대 위치까지 모든 자석을 배치할 수 있는지 검사합니다.

배치가 가능하다면 해당 거리를 정답 후보로 저장하고, 더 큰 거리도 가능한지 탐색 범위를 위쪽으로 좁혀 나갑니다. 배치가 불가능하다면 탐색 범위를 아래쪽으로 줄입니다. 이 과정을 반복하면 최소 거리가 최대화되는 값을 찾을 수 있습니다.

canPlace 함수는 현재 거리 조건(mid)으로 C개의 자석을 모두 배치할 수 있는지 확인하는 역할을 하며, minDistMax 함수가 전체적인 이진 탐색을 수행합니다.

구현 예제

위 접근 방식을 구현한 프로그램은 다음과 같습니다.

#include <iostream>
using namespace std;
bool canPlace(int arr[], int n, int C, int mid){
    int magnet = 1, currPosition = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] - currPosition >= mid) {
            magnet++;
            currPosition = arr[i];
            if (magnet == C)
                return true;
        }
    }
    return false;
}
int minDistMax(int n, int C, int arr[]){
    int lo, hi, mid, ans;
    lo = 0;
    hi = arr[n - 1];
    ans = 0;
    while (lo <= hi) {
        mid = (lo + hi) / 2;
        if (!canPlace(arr, n, C, mid))
            hi = mid - 1;
        else {
            ans = max(ans, mid);
            lo = mid + 1;
        }
    }
    return ans;
}
int main(){
    int C = 4;
    int arr[] = { 1, 4, 6, 12, 28, 44 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"Maximised Minimum distance is "<<minDistMax(n, C, arr);
    return 0;
}

실행 결과

Maximised Minimum distance is 11

시간 복잡도

이진 탐색의 각 단계마다 canPlace 함수가 O(n) 시간에 배치 가능 여부를 검사하므로, 전체 시간 복잡도는 O(n log D)입니다. 여기서 D는 탐색 범위(최대 위치 값)입니다. 이러한 특성 덕분에 입력 크기가 커져도 효율적으로 동작합니다.