[ 백준 ] 2110번 - 공유기 설치 (Python)

기본 정보

• Level: gold 5
• Problem Link: 공유기 설치
• Problem Number: 2110
• My Solution Link: 나의 풀이
• Algorithm I used : 이진탐색(binary search)

문제

• N개의 집에 C개의 공유기 설치
• 한 집에는 공유기 하나만
• 가장 인접한 두 공유기 사이의 최대 거리?
• 실제 공유기를 설치하는 집 간의 간격은 정확하게 주어진 간격만큼 일수도 있고 그보다 더 멀 수도 있다.

알고리즘

• [1,집 위치 중 최댓값] 범위에서 이진탐색 실행
• 위치를 기준으로 range를 좁혀가며 실행
• scan range 내에서 middle 단위가 몇 번인지 counting

1차 시도

• 로직이 맞다고 생각했고, 테스트 케이스도 맞았으나 채점 결과 틀렸다고 처리되었다.

# 집의 개수, 공유기의 개수
n, c = map(int,input().split())

# 각 집의 좌표
houses = [int(input()) for _ in range(n)]

left, right = min(houses), max(houses)

while left <= right:
    middle = (left + right) // 2
    
		# middle 단위가 몇 번이나 나오나 체크
    wifi_router = max(houses) // middle

    if wifi_router < c:
        right = middle - 1
    else:
        left = middle + 1

print(right)

다시 생각한 알고리즘

• 위의 방법 외에는 떠오르지 않아 구글링 후 재시도했다.
• left, right를 좌표가 아니고 거리로 두자.
  • left : 최소거리 (1; 거리 단위가 1이므로)
  • right : 최대거리 (max(houses) - min(houses))
• (현재 집의 위치 - ‘이전’에 공유기 설치한 ‘위치’) ≥ (middle)이면 count + 1
  • 공유기 설치 위치를 저장할 배열이 필요하다.
  • 첫번째 집에는 무조건 설치하는 것으로 가정???

2차 시도

• 시간 초과가 발생했는데, 언어 설정의 문제였다. (Python3 → PyPy3)

# 집의 개수, 공유기의 개수
n, c = map(int,input().split())

# 각 집의 좌표
houses = sorted([int(input()) for _ in range(n)])

# 최소거리, 최대거리
left, right = 1, max(houses)-min(houses)

while left <= right:
    middle = (left + right) // 2  # 우리가 찾게될 최적의 설치 간격
    
    routers = [min(houses)]  # 설치한 공유기의 각 위치; 첫번째 집은 무조건 설치하는 것으로 가정

    for house in houses:
        if house - routers[-1] >= middle:  # 현재 집 위치와 이전에 설치한 공유기의 위치 간의 거리가 middle 이상이 되면 설치가능하므로
            routers.append(house)

    if len(routers) < c:
        right = middle - 1
    else:
        left = middle + 1

print(right)