백준 2110번: 공유기 설치

문제 링크 : https://www.acmicpc.net/problem/2110

참고한 블로그 : https://katfun.tistory.com/67



이분 탐색을 이용해서 상황을 만족하는 특정 변수의 최대, 최솟값을 구하는 문제를 파라메트릭 서치라고 하나보다. 같은 유형으로 분류된 다른 문제 중 나무 자르기 문제는 스스로 생각해서 풀어서 이 정도는 금방 할 수 있을 줄 알았다.

근데 이번 문제는 도대체 어디서 무엇을 기준으로 이분 탐색을 진행해야 할 지 도저히 생각이 나지를 않았다. 보통은 블로그를 참고할 때 코드는 보지 않고 풀이한 생각정도만 읽고 이해한 후 직접 코드를 짜는 식으로 했었는데, 이번건 왜인지 코드도 잘 못짜겠었달까.. 아직 여러 문제를 접해보지 않아서겠지?

그리고 이분 탐색 문제에서 제일 헷갈리는건 조건문에서 부등호를 적을 때 등호가 들어가느냐 마느냐이다. 등호가 들어가고 안들어가고에 따라서 결과가 엄청 달라지던데.. 어렵다 어려워. 하다보면 늘겠지.
<작성한 코드>

#include <iostream>
#include <algorithm>
#define max(a, b) (a > b ? a : b)
using namespace std;

long long a[200001]; // 집 위치
long long n, c; // n = 집 개수, c = 공유기 개수

int main()
{
    scanf("%d %d", &n, &c);
    for(int i = 0; i < n; i++){
        scanf("%d", &a[i]);
    }
    sort(a, a + n);
    
    long long start = 1, end = a[n - 1] - a[0], mid, result = -1;
    while(start <= end){
        mid = (start + end) / 2; // 간격
        
        long long house = a[0], cnt = 1;
        for(int i = 1; i < n; i++){
            if(a[i] - house >= mid){
                cnt++; // 공유기 설치
                house = a[i];
            }
        }

        if(cnt >= c){ // 공유기가 많으면 간격 늘임
            start = mid + 1;
            result = max(result, mid);
        }
        else{
            end = mid - 1;
        }
    }
    printf("%d", result);
}

이분 탐색 문제는 대부분 값의 범위를 엄청 크게 설정을 해둬서 long long 타입을 많이 쓰더라. 그래서 혹시 몰라 int로 했다가 오류가 뜨는 상황을 막으려고 int를 써도 되는 변수도 전부 long long 타입으로 선언했는데, 실전에서는 이런 것도 전부 고려해서 타입을 맞게 짜야겠지.

• int의 범위 : –2,147,483,648 ~ 2,147,483,647, 2의 31승 - 1