2110번 - 공유기 설치

출처: 백준 알고리즘

주소: www.acmicpc.net/problem/2110

2110번: 공유기 설치

2110번 공유기 설치

문제 요약:

-> N개의 좌표에서 C개의 공유기를 설치하는데, 인접한 두 공유기 사이의 최대 거리를 계산

 

해결 방법:

1) C - 2번의 이분 탐색을 계속 진행하는 방법

 => 이렇게 하면 계산량과 저장공간이 너무 많이 들어서 비효율적이다.

 => 아래 그림처럼 x1 > x2인 경우에 x1을 분할하면서 C개의 공유기를 찾는 방식이다.

2) "인접한 두 공유기 사이의 거리"를 변수(d)로 두고 이분 탐색하는 방법

  (1) d의 최소값을 min_val으로 정하고, d의 최대값을 max_val으로 설정.

  (2) mid_val = (min_val + max_val) / 2 으로 중간값을 계산.

  (3) min_val <= max_val 동안 반복.

  (4) 인접한 두 공유기의 계산하면서 mid_val보다 큰 값 인 개수(cnt)을 계산.

  (4-1) cnt가 C보다 크거나 같으면, mid_val을 키우기 위해 min_val = mid_val + 1으로 설정.

  (4-2) cnt가 C보다 작으면, mid_val을 줄이기 위해 max_val = mid_val - 1으로 설정.

  (5) min_val > max_val이면 반복문을 나오게 되고, 그 때의 mid_val를 정답으로 출력.

 

 

소스 코드:

#include <iostream>
#include <vector>
#include <algorithm>
 
int c_divide(std::vector<int>& x, int min_val, int max_val, int c) {
    // 제일 작은 간격: min_val
    // 제일 큰 간격: max_val
    // 중간 간격: mid_val
    // 중간 간격보다 큰 경우를 카운트하는 변수: cnt
    int mid_val = (min_val + max_val) / 2;
    int cnt, left_x, right_x;
 
    // 최소 간격이 최대 간격보다 작은 경우 반복
    while (min_val <= max_val) {
        // (최대 간격 - 최소 간격)이 항상 중간 간격보다 크기 때문에
        // 초기값을 1로 설정
        cnt = 1;
 
        // 왼쪽 x값 초기화
        left_x = x.front();
        // 모든 인덱스를 반복
        // 왼쪽 x값을 0으로 하였기 때문에
        // 인덱스를 1부터 시작
        for (int i = 1; i < x.size(); i++) {
            // 오른쪽 x값 대입
            right_x = x[i];
            // 오른쪽 x - 왼쪽 x값이 중간 간격보다 크거나 같으면
            if (right_x - left_x >= mid_val) {
                // 왼쪽 x에 오른쪽 x를 대입
                left_x = right_x;
                // cnt값 한개 증가
                cnt++;
            }
        }
        // cnt이 c보다 작은 경우
        // mid_val을 줄여야 하기 때문에
        if (cnt < c) {
            max_val = mid_val - 1;
        }
        // cnt이 c보다 크거나 같은 경우
        // mid_val을 키워야 하기 때문에
        else {
            min_val = mid_val + 1;
        }
 
        // 중간 간격 갱신
        mid_val = (min_val + max_val) / 2;
    }
 
    return mid_val;
}
 
int main() {
    // 변수 설정
    int n, c, res;
    std::vector<int> x;
 
    // 입력
    scanf("%d %d", &n, &c);
    for (int i = 0; i < n; i++) {
        int tmp;
        scanf("%d", &tmp);
        x.push_back(tmp);
    }
 
    // 정렬
    std::sort(x.begin(), x.end());
 
    // 계산
    // 제일 작은 간격: min_val
    // 제일 큰 간격: max_val
    int min_val, max_val;
    min_val = 1;
    max_val = x.back();
    res = c_divide(x, min_val, max_val, c);
 
    printf("%d\n", res);
 
    return 0;
}

 

한줄평:

-> 기준이 되는 값을 어느 것으로 두는 지에 따라 계산의 편의성이 달라진다.