[백준(BOJ)] 2110번 : 공유기 설치 - C++[CPP]

www.acmicpc.net/problem/2110

2110번: 공유기 설치

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 이분 탐색
• 매개 변수 탐색

 

---

 

⊙ 문제 접근 과정

 

문제 요약: 공유기를 설치할 건데 가능한 멀리 설치하고 싶다. (같은 좌표는 없다)

 

여러 풀이방법이 있지만 이진 탐색 알고리즘을 사용하여 문제에 접근했다.

이진 탐색을 이용하여 문제를 풀 때 index가 아닌 거리로 두고 풀어야 한다. (거리기준)

 

1. n(집의 개수), c(공유기 개수), x(집 좌표) 값 입력받는다.
2. x값 정렬
3. 거리 기준으로 이진 탐색
4. 결괏값 출력

무엇을 기준으로 잡을지 애먹었다.

 

---

 

⊙ 문제 풀이

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n,c;
vector<int> x;

int main() {
    cin >>n>>c;
    for(auto i =0; i<n;i++) {
        int a;
        cin >> a;
        x.push_back(a);
    }
    sort(x.begin(),x.end());

    int start=0;
    int end=x[n-1];
    int result=0;
    int temp,count;

    while(start<=end) {
        int mid = (start+end)/2;
        temp=0, count =1;
        for(auto i=1;i<n;i++) {
            if(x[i]-x[temp]>=mid) {
                temp=i;
                count++;
            }
        }

        if(count>=c) {
            result=mid;
            start=mid+1;
        }else {
            end=mid-1;
        }
    }
    cout <<result;
}

 

---

⊙ 결과

 

 

---

⊙ 마무리

 

푸는데 어려웠다 ㅠ

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!