2110-공유기

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

2110번: 공유기 설치

이제까지 풀던 이분탐색 문제의 조오금 고급 버전..! 전체적인 구성은 이전의 문제들과 동일하지만 is_possible에서의 조건을 조금 더 구체적으로 분리해 주어야 한다. 

 

사이트에 반례가 많이 없어서 예외처리를 해주는데 시간이 조금 걸렸다. 내 코드가 조금 더러운것 같기도.?

 

1. lo, hi, mid를 정할때, mid는 배열의 (최대-최소) // 공유기 개수 로 놓고 lo의 초기상태는 1로 두어야 한다.

   처음에는 lo를 min(house)로 두었는데 이러면 거리가 아닌 하우스 위치의 최솟값이 초기 상태가 되어버려 답이 출력되지 않을 수 있다.

 

2. 공유기의 개수(C) 가 2일때는 is_possible를 실행하면 안된다. 나의 경우 is_possible에서 예외처리를 하였는데 그냥 C가 2이면 배열의 최대-최소로 답을 출력하는게 더 깔끔한 방법일듯 하다

 

3. 괄호 방향, 부등호 잘 확인하자 -> 이분 탐색 문제를 풀 때 항상 살짝은 헷갈리는 부분이다. 실행과정을 따라가면서 자세히 조건을 달아주자

      

      

      

    
    

      <python />
    
import sys
input = sys.stdin.readline
N, C = map(int, input().split())
house = sorted([int(input()) for _ in range(N)])
lo = min(house)
hi = max(house)
mid = (hi-lo) // C
lo = 1

def is_possible(mid):
    cnt = C-2
    last = 0
    if cnt == 0:
        print(max(house)- min(house))
        exit(0)
    for i in range(1, N-1):
        if house[i] - house[last] >= mid:
            last  = i
            cnt -= 1
            if cnt == 0 and house[N-1] - house[i] < mid:
                return False
    if cnt > 0:
        return False
    else:        
        return True

ans = 0
while lo <= hi:
    if is_possible(mid):
        lo = mid+1
        ans = mid
    else:
        hi = mid -1
    mid = (lo + hi) // 2
print(ans)