[BOJ/C++]2110번_공유기 설치(★)

https://www.acmicpc.net/problem/2110

 

##문제 이해하기

 

##코드 작성 전 알아야 할 개념 && 코드 논리 :

1_ 첫번째 집을 공유기를 설치했다고, 가정 => 그 다음 순차탐색으로 집을 순회하면서, 다음 공유기를 설치할 집을 찾는 IDEA

if (mid <= 순회하면서, 공유기 설치한 집과의 인접 거리) : 공유기 설치개수++ , 인접 공유기 변수 업데이트

(자세한 설명은 밑의 노트)

2_ (1_)과정의 집을 순회하면서, 공유기 설치 후 => 설치된 공유기 개수 vs 입력한 공유기를 설치해야할 개수(C) 비교

=> 이분탐색

3_★Upper_Bound 이분탐색 vs Basic 이분탐색 :

어떤 값을 찾는 것이 아닌, 조건에 맞지만, 그 중 최대거리를 찾는 과정이기 때문에, Upper_Bound로 코드 구현해야한다.

※참고 설명 :

일반적인 이분 탐색 (Binary Search)

일반적인 이분 탐색은 주로 정렬된 배열에서 특정 값을 찾을 때 사용됩니다. 이 경우에는 특정 값이 배열에 존재하는지를 확인하는 것이 목표입니다.

• 사용 상황: 배열이나 리스트에서 특정 값의 존재 여부를 확인하거나, 특정 값을 찾는 경우.
• 예시 문제: 정렬된 배열에서 숫자 7이 있는지 확인하는 문제.

상한/하한 경계를 찾는 이분 탐색 (Upper Bound/Lower Bound)

상한 경계(Upper Bound)나 하한 경계(Lower Bound)를 찾는 이분 탐색은 주로 값의 범위를 다루는 문제에서 사용됩니다. 여기서 Upper Bound는 특정 값보다 큰 첫 번째 위치를, Lower Bound는 특정 값보다 크거나 같은 첫 번째 위치를 의미합니다. 이 경우, 값 자체를 찾는 것이 아니라 값이 위치할 수 있는 범위를 찾는 것이 목표입니다.

• 사용 상황: 배열이나 리스트에서 특정 값보다 크거나 작은 값이 처음으로 나타나는 위치를 찾거나, 특정 조건을 만족하는 최대 또는 최소 값을 찾는 경우.
• 예시 문제: 정렬된 배열에서 특정 값보다 크거나 같은 첫 번째 위치를 찾는 문제, 또는 두 요소 사이의 최대/최소 간격을 찾는 문제.

Upper Bound를 사용한 이분 탐색 예시

주어진 문제(공유기 설치 문제)는 Upper Bound를 사용하여 해결할 수 있는 전형적인 예입니다. 여기서는 두 공유기 사이의 최대 거리를 찾기 위해 Upper Bound를 사용하여 가능한 최대 간격을 탐색합니다. 이는 특정 간격(mid)을 기준으로 공유기를 설치할 수 있는지 여부를 확인하며, 가능한 최대 간격을 탐색하는 과정입니다.

문제 예시

• 문제: N개의 집에 C개의 공유기를 설치할 때, 가장 인접한 두 공유기 사이의 거리를 최대로 하려면 그 최대 거리는 얼마인가?
• Upper Bound 사용 이유: 특정 간격(mid)을 기준으로 공유기를 설치할 수 있는지 확인하고, 가능한 최대 거리를 탐색하는 것이 목표입니다.

Lower Bound를 사용한 이분 탐색 예시

Lower Bound는 주어진 값 이상이 처음 나타나는 위치를 찾는 데 사용됩니다. 이는 특정 값보다 작지 않은 첫 위치를 찾는 데 유용합니다.

##코드 논리 분석 노트 :

##코드 :

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
void init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
 
int main() {
    init();
    int N, C;
    cin >> N >> C;
 
    vector<unsigned int> V(N);
    for (int i = 0; i < N; i++) {
        cin >> V[i];
    }
 
    // 오름차순 정렬
    sort(V.begin(), V.end());
 
    unsigned int start = 1;//두 인접한 공유기의 최소 거리(모든 경우의 수 중)
    unsigned int end = V[N - 1] - V[0];//입력된 공유기들 중 가장 먼 거리
    unsigned int ans = 0;
 
    // 이분 탐색
    while (start <= end) {
        unsigned int mid = (start + end) / 2;
 
        //맨 첫번째 집을 공유기 설치했다고, 가정
        int cnt = 1;//설치된 공유기 개수
        unsigned int last_h = V[0];//공유기가 설치된 첫번째 집의 위치
 
        for (int i = 1; i < N; i++)//2번째 집부터 스캔 
        {
 
            if (V[i] - last_h >= mid) //이분 탐색된 거리 vs 공유기의 사이 거리 비교
            {
                //공유기 거리 >=거리
                cnt++;//공유기 설치
                last_h = V[i];//인접 공유기 업데이트
            }
 
        }
 
        //Upper Bound
        if (cnt>=C) 
        {
            ans = mid;
            start = mid + 1;
        }
        else {
            end = mid - 1;
        }
    }
 
    cout << ans << '\n';
 
    return 0;
}