[알고리즘] 크래프톤 정글 혼자 못 푼 문제 정리(공유기 설치)

BOJ 2110 공유기 설치

난이도 : (백준 난이도 기준) 골4, (크래프톤 정글 기준) 중

사용 알고리즘 or 자료 구조 : 이분탐색, 매개변수 탐색

처음 생각한 풀이

처음에는 입력 받은 집의 위치를 정렬을 한 뒤, 시작 집과 끝 집에 공유기가 반드시 설치된다고 생각하고 이상적으로 생각했을 때 공유기끼리의 거리가 얼마나 되어야할지 생각했다.

 

입력값으로 생각하면 idealD = (house[N - 1] - house[0]) / (C - 1) 가 되어야한다.

 

그래서 시작 index를 0으로 두고 거리가 idealD가 되는 집이 있으면 해당 집의 index를 반환하고, 없으면 해당 위치에 더 가까운 집의 index를 반환하는 식으로 이분탐색을 구현하려 했다.

 

하지만 예제와 게시판에 올라온 반례가 모두 맞았음에도 계속해서 1퍼 혹은 0퍼에서 틀렸습니다 가 떠서 어쩔 수 없이 구글링을 통해 접근법을 살펴보았다.

구글링 이후 풀이

내가 생각했던 풀이와 전혀 다른 접근법이었다.

 

이분탐색을 설치할 집의 index를 찾는 데 쓰는 것이 아닌, 공유기 사이의 최대 거리를 찾는데 써야했다.

 

먼저 공유기 사이의 최소 거리를 1로, 최대 거리를 시작 집 ~ 끝 집까지의 거리(house[N - 1] - house[0]) 으로 두고 시작한다.

 

그 뒤, 이분탐색으로 공유기 C개 이상이 들어갈 수 있는 최대 거리를 계속해서 찾아나가면 된다.

 

자세한건 코드와 코드에 달아놓은 주석을 통해 이해할 수 있다.

 

 

 

 

 

 

 

 

 

 

 

 

 

※ 스 포 주 의 ※

 

 

 

 

 

 

 

 

 

 

 

 

코드

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int N, C;

vector<long long> house;

int main() {

    cin >> N >> C;

    for(int i = 0; i < N; i++) {

        long long tmp;

        cin >> tmp;

        house.push_back(tmp);

    }

    sort(house.begin(), house.end());

    long long start = 1;

    // 최소 거리 = 1

    long long end = house[N - 1] - house[0];

    // 최대 거리 = 시작 집 ~ 끝 집 거리

    long long ans = 0;

    while(start <= end) {

        long long mid = (start + end) / 2;

        // 공유기를 설치하는 데 사용할 최소 거리

        long long prev = house[0];

        int cnt = 1;

        for(int i = 1; i < N; i++) {

            if(house[i] - prev >= mid) {

                // 순회를 돌며 사용할 거리 이상인 집이 보이면 설치

                cnt++;

                prev = house[i];

            }

        }

        if(cnt >= C) {

            // 설치한 공유기 개수가 C보다 많으면 사용할 거리를 좀 더 늘려서 사용(지금도 정답으로 사용 가능하지만 최적의 해를 찾아야함)

            ans = max(ans, mid);

            start = mid + 1;

        }

        else if(cnt < C) {

            // 설치한 공유기 개수가 부족하면 사용할 거리를 줄여야함

            end = mid - 1;

        }

    }

    cout << ans;

    return 0;

}