백준 2110. 공유기 설치 [실패]

1.실패 원인

조금 변형된 이분 탐색.. 해내지 못했다 ㅠ. 일단 기본적인 이분탐색 특징은 그대로 사용된다. 단, 문제에서 무얼 원하는지 (여기서는 거리) 파악 한 후 변수들을 설정해주어야 한다. 그리고 유망한 조건을 찾아낼 때도 문제에서 무얼 원하는지 확실히 파악해서 결과를 내놓아야 한다. Promising은 유망한지 유망하지 않은지를 결정해 유망하면 (여기서 유망하다는 의미는 반으로 더 쪼갤 수 있는가를 말한다.) 최대치(공유기 간격의 최대)를 조정하고 유망하지 않으면 최소치(공유기 간격의 최소)를 조정한다. 쉽게 말해서 설치해야하는 공유기 개수보다 많이 설치된 경우는 유망하니 더 쪼개서 개수를 맞춰야 한다는 것이다.

 

밑의 코드를 보면 이웃한 집들의 거리를 비교하여 탐색 조건이되는 거리보다 크면 카운트를 증가시킨다. 그 카운트가 문제에서 요하는 공유기 개수보다 많거나 같다면 유망하다고 판단한다. 문제에서 요하는 공유기 개수보다 카운트가 크다는 것은 집 사이의 간격을 더 증가시켜도 된다는 의미이다. 그러다가 특정 간격에 대해서 카운트수와 문제에서 요하는 공유기 개수가 같아진다면 그것이 답으로 채택될 것이다. 

 

2.작성 코드

#include <iostream>

#include <algorithm>

using namespace std;

 

const int MAX = 200000;

 

int N, C;

int house[MAX];

 

bool possible(int dist)

{

        int cnt = 1;

        int prev = house[0];

        //조건 충족하는지 확인

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

                 if (house[i] - prev >= dist)

                 {

                         cnt++;

                         prev = house[i];

                 }

       

        //조건 충족

        if (cnt >= C)

                 return true;

        return false;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N >> C;

 

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

                 cin >> house[i];

 

        sort(house, house + N);

 

        //최소거리, 최대 거리

        int low = 1, high = house[N - 1] - house[0];

        int result = 0;

        while (low <= high)

        {

                 int mid = (low + high) / 2;

                 if (possible(mid))

                 {

                         result = max(result, mid);

                         low = mid + 1;

                 }

                 else

                         high = mid - 1;

        }

        cout << result << "\n";

        return 0;

}



//출처: https://jaimemin.tistory.com/966 [꾸준함]

3.참고 코드

https://jaimemin.tistory.com/966

백준 2110번 공유기 설치

 

4. 해결 방안

다음을 기억하자.

1. 이분탐색의 Promising은 조건을 충분히 만족하는 경우(조건 값 이상일 때) true를 반환한다.

2. Promising의 매개변수로 들어갈 조건 값은 문제에서 무엇을 요구하는지에 따라 달라진다.