[백준] 2110번 공유기 설치

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

이진 탐색으로 푸는 문제 같은데 중간점을 이용해서 공유기 개수를 세는 방법이 떠오르지 않아 구글링을 통해 해결했다.

생각하지 못했던 부분은 다음과 같다.

• 시작점은 집들 사이의 최솟값, 끝점은 집들 사이의 최댓값으로 설정

• 공유기 위치는 현재위치와 다음 집이 공유기 사이의 거리 이상인 곳에 설치

이 문제는 sys.readline 을 사용해서 입력값을 받지 않으면 시간 초과가 발생한다.

# 2110 : 공유기 설치

import sys
input = sys.stdin.readline

n, c = map(int, input().split())
house = [int(input().rstrip()) for _ in range(n)]

house.sort()

# 끝점은 집들 사이 거리의 최댓값
start, end = 1, (house[-1] - house[0])

result = 0
while start <= end:
    mid = (start + end) // 2
    current = house[0]
    # 시작점은 공유기 설치하므로 1로 초기화
    count = 1

    for i in range(1, len(house)):
        # 현재 위치와 다음 집 사이의 거리가 mid 이상인 위치에만 공유기 설치
        if house[i] - current >= mid:
            # 현재 위치 바꾸기
            current = house[i]
            count += 1
    
    # 공유기가 부족하면 mid 거리 크게
    if count >= c:
        result = mid
        start = mid + 1
    # 공유기가 남으면 mid 거리 작게
    else:
        end = mid - 1

print(result)

Uploaded by Notion2Tistory v1.1.0