[백준/BOJ] 2110번 : 공유기 설치, 1300번 : K번째 수 (이분 탐색)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 2110번 : '공유기 설치', 1300번 : 'K번째 수' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Gold 티어에 해당하며, 문제를 풀이하기 위해 이분 탐색(Binary Search) 알고리즘에 대한 이해가 필요합니다.

 

 

2110번 : 공유기 설치

 

N개의 집의 좌표가 주어졌을 때, C개의 공유기를 최대한 거리가 서로 멀리 떨어지도록 설치했을 때 공유기 사이의 거리를 구하는 문제입니다.

언뜻 보기에는 고려해야 할 변수가 많기 때문에 공유기 간 최대 거리를 바로 구하는 알고리즘을 찾기 쉽지 않습니다.

그렇기 때문에 이런 경우에는 공유기의 거리 자체를 아무거나 잡고 시작하여 범위 내에서 이분 탐색을 수행하는 방식으로 해결 할 수 있습니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, C; cin >> N >> C;

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

    int Left = 1, Right = arr[N-1], ans = 0;
    while(Left <= Right) {
        int Mid = (Left + Right)/2;
        int cnt = 1, before = arr[0];

        for(int i=1; i<N; i++)
            if(arr[i] - before >= Mid) {
                cnt++;
                before = arr[i];
            }

        if(cnt >= C) {
            ans = Mid;
            Left = Mid + 1;
        }
        else Right = Mid - 1;
    }
    cout << ans;
}

 

위의 코드에서 while문 내의 Mid 값이 임시로 잡은 공유기 간 최소 거리에 해당합니다.

공유기 간 최소 거리 이상 떨어진 지점 사이에 공유기를 설치할 수 있는대로 최대한 설치한 뒤 설치된 공유기의 수를 확인하여, C개 이상 설치된 경우 중 거리 값의 최댓값을 구하여 답으로 출력해주면 됩니다.

 

 

 

 

1300번 : K번째 수

 

A[i][j] = i*j인 N×N 배열을 1차원 배열에 오름차순으로 정렬하여 저장했을 때, k번째 원소를 구하는 문제입니다.

즉, 1 <= i, j <= N인 i*j들 중 k번째로 작은 수를 구하면 됩니다.

 

N <= 10^5이므로, O(N log N) 이하의 알고리즘으로 짜야만 시간초과를 피할 수 있음을 알 수 있습니다.

따라서 K = i*j로 나타낼 수 있는 (i, j)의 조합이 K개보다 많을 수 없으므로 1<=B[K]<=K 내에서 B[K]에 대한 이분 탐색을 수행하며 답을 찾으면 됩니다.

(저는 직관적, 대략적으로 잡았으나 엄밀한 증명을 해서 잡아도 되고 아니면 아예 넉넉하게 상한을 2K로 잡아도 됩니다.)

 

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, K; cin >> N >> K;

    int Left = 1, Right = K, ans;
    while(Left <= Right) {
        int Mid = (Left + Right)/2;
        long long cnt = 0;

        for(int i=1; i<=N; i++)
            cnt += min(Mid/i, N);

        if(cnt >= K) {
            ans = Mid;
            Right = Mid - 1;
        }
        else Left = Mid + 1;
    }
    cout << ans;
}

 

따라서 위와 같이 B[K] 값을 Mid로 가정한 뒤 이분 탐색을 수행해주면서 Mid 값 이하의 i*j가 되는 (i, j) 순서쌍의 수를 계산해서 K 이상이면서 가장 가까운 Mid를 찾아주면 됩니다.

B[K]가 몇 번째 수인지를 찾는 방법은, i=1부터 N까지 돌아가면서 Mid/i 값을 더해주면 됩니다.

그러나 Mid가 N보다 큰 경우 Mid/i 값이 N보다 커질 수 있기 때문에 이 경우는 상한선인 N을 넘지 못하도록 cnt += min(Mid/i, N)과 같이 계산해주어야 합니다.

 

cnt = K가 아닌 cnt >= K인 경우에 대해 ans = Mid로 갱신하는 이유는, cnt > K일 때도 답이 나올 수 있기 때문입니다.

예를 들어 문제에서 주어진 예제에서 7번째 수는 6이지만 cnt = 8이기 때문입니다. (1, 2, 2, 3, 3, 4, 6, 6으로 6이 1개보다 많기 때문에 나오는 결과)

따라서 위와 같이 cnt >= K인 경우에 대해서도 ans = Mid로 갱신해주어야 합니다.

 

 

 

---

 

이상으로 이분 탐색까지도 모든 문제들을 풀이해보았습니다.

다음 포스트에서는 우선순위 큐와 관련하여 아직 풀이하지 않은 문제들을 2문제 풀이해보도록 하겠습니다.