[BOJ] 2110 공유기 설치_Binary Search

공유기 설치

link

내 풀이

• 방식 : Binary Search
• binary search 중에서도 Parameter를 찾는 문제

📰code(python)

N,C = list(map(int,input().split()))
arr = []
for _ in range(N):
    arr.append(int(input()))

sorted_arr = sorted(arr)
part = C-1 # part개 만큼의 영역이 필요함

# binary search를 위한 영역
start = 1
end = (sorted_arr[-1]-sorted_arr[0])//part+1

# 공유기간 거리가 mid일 경우 설치 가능여부 확인
def router(mid):
    val = sorted_arr[0]+mid
    p = part
    for i in range(1,N):
        if sorted_arr[i]>=val:
            p-=1
            val = sorted_arr[i]+mid
            if p==0 : return 1
    return 0

while end > start+1:
    mid = (start+end)//2
    start,end = (mid,end) if router(mid) else (start,mid)
print(start)

📰code(C++)

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

int n, c, arr[200002];
int val,p;

inline int router(int mid){
    val = arr[0]+mid;
    p = c-1;
    for(int i=1;i<n;i++){
        if (arr[i]>=val){
            p--;
            val = arr[i]+mid;
            if (p==0) return 1;
        }
    }
    return 0;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> c;
    for(int i = 0; i<n; i++)
        cin >> arr[i];
    
    sort(arr,arr+n);
    
    int left = 1, right = (arr[n-1]-arr[0])/(c-1)+1;
    int mid,answer;
    answer = 1;
    while (left<right){
        mid = (left+right)/2;
        if (router(mid)==1){
            answer=mid;
            left = mid+1;
        }
        else right = mid;
    }
    cout<<answer;
}

💡 수정 필요한 내용은 댓글이나 메일로 알려주시면 감사하겠습니다!💡