[Baekjoon]백준 2110 공유기 설치(골드 4) - C++, Python

문제설명

문제를 살펴보면 공유기의 위치가 각각 주어진다 이후 C개의 공유기를 두어야하는데, 놔두었을 때

각 사이의 거리를 최대가 되도록 만들어야한다

이전에 이분탐색 단계에서 계속해서 풀었기 때문에 이번에도 기준을 쉽게 정할 수 있었다

 

일단 각 거리에 대한 정보를 sort()를 통해 정렬을 해주어 가장 긴 거리가 마지막 index에 위치하도록 하였다

그리고 시작 지점(최소거리)을 1, 끝지점(가장 먼 두 집 사이의 거리)을 첫 지점에서 끝지점까지의

최대 거리로 설정하여 값을 갱신하며 공유기를 놓을 수 있는 경우의 수에 대해 조사하게 된다

여기서 중요한 점은 이 문제는 다른 문제들과 다르게 거리에 따라 공유기를 두어야하기 때문에

이전에 위치한 공유기의 위치를 저장해주어야한다 따라서 prev_house라는 변수를 추가해주었다

그리고 해당 변수는 가장 첫번째 지점의 값으로 초기화해준다

이후에는 탐색을 반복하며 놓을 수 있는 거리인지 확인하고, 최종적으로 놔둔 공유기의 개수가

기준치보다 작다면 거리(mid)를 줄이고(end = mid - 1), 기준치보다 크다면 거리(mid)를 늘린다(start = mid + 1)

또한 해당 거리(mid)를 결과값으로 저장하고 이를 계속해서 갱신하게 된다

이렇게 result의 값을 저장하다보면 설치가능한 거리 중 가장 큰 값이 저장된다

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int house_num, router;
    cin >> house_num >> router;

    vector<int> house(house_num);
    for(int i = 0; i < house_num; i++)
        cin >> house[i];
    
    sort(house.begin(), house.end());

    int start = 1; // 최소 거리
    int end = house[house_num-1] - house[0]; // 최대 거리
    int result = 0;
    while (start <= end) {
        int mid = (start + end) / 2;
        int cnt = 1;
        int prev_house = house[0]; // 이전 설치 위치
        for(int i = 1; i < house_num; i++) {
            if(house[i] - prev_house >= mid) {
                cnt++;
                prev_house = house[i]; // 설치 위치 갱신
            }
        }
        if(cnt >= router) {
            result = mid;
            start = mid + 1;
        }
        else
            end = mid - 1;
    }

    cout << result << endl;

    return 0;
}

이번에는 먼저 C++로 작성하고, Python으로 작성하였다

import sys
input = sys.stdin.readline

house_num, router = map(int, input().split())
house = []
for _ in range(house_num):
    house.append(int(input()))
house.sort()

start, end = 1, house[-1] - house[0]
result = 0
while start <= end:
    mid = (start + end) // 2
    cnt = 1
    prev_house = house[0]
    for i in range(1, house_num):
        if house[i] - prev_house >= mid: 
            cnt += 1 
            prev_house = house[i]
    if cnt >= router:
        result = mid
        start = mid + 1
    else:
        end = mid - 1
        
print(result)