[BOJ] #2110 공유기 설치 (이분탐색, Python)

🌱 문제

2110번: 공유기 설치

 

🌱 풀이

이 문제는 이분탐색 문제입니다. 이 문제에서는 집들 사이의 간격을 이분탐색하여 조정합니다. 아래에서 자세히 설명해보겠습니다.

0. 입력 받기

  

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

 

• 집의 개수 n과 공유기 개수 c를 입력 받습니다.
• 집의 위치를 리스트(position)에 입력받습니다.
• 이분 탐색을 위해서 집의 위치를 정렬합니다.

 

1. 변수 초기화

  

    
    
    
    
  
result = 0
start,end = 1, position[n-1] - position[0]

• 문제의 정답인 공유기의 최대 간격을 저장하는 result 변수를 생성합니다.
• 이분 탐색을 위한 start와 end를 생성합니다. 이때, 간격을 이분탐색하여 조정할 것이기 때문에 start의 초기값은 간격의 최솟값인 1이고, end의 초기값은 간격의 최댓값인 position[n - 1] - position[0] 입니다.

 

2. 이분 탐색

  

    
    
    
    
  
while(start < end):
    mid = (start + end)//2

    # 첫번째 집에는 무조건 설치
    count = 1
    installed = position[0]

    for i in range(n):
        if position[i] - installed >= mid:
            count += 1
            installed = position[i]    # 공유기 설치
    if count >= c:
        result = mid
        start = mid + 1     # 간격 늘리기
    elif count < c:
        end = mid       # 간격 줄이기

• 중간값(mid)는 (start + end) // 2입니다. 즉, 간격의 중간값입니다. (start가 간격의 최솟값, end가 간격의 최댓값)
• 공유기를 최대한 널찍널찍하게 설치하기 위해서는 첫번째 집에는 무조건 설치되어야 합니다. (단, 마지막 집에는 무조건 설치하지 않을 수 있습니다. 따라서 while 룹으로 들어가면 공유기 설치 개수를 새는 count 변수를 무조건 1로 설정하고 position[0]을 공유기 설치 위치를 저장하는 installed 변수에 할당합니다. 
• 그리고 나서, 전체 position을 돌면서 현재 설정된 mid 값보다 간격이 넓거나 같은 위치에 공유기를 설치합니다.
  • 공유기를 설치했으면 count 값을 1 증가시키고 installed는 설치한 공유기의 위치로 갱신시킵니다.
• for 루프를 모두 돌고 나면 현재 설정한 mid값보다 크거나 같은 간격을 두고 설치할 수 있는 공유기를 모두 설치했다는 의미입니다.
  • 설치한 공유기 개수(count)가 설치해야 하는 공유기 개수(c)보다 크거나 같다면 현재 mid가 정답이 될 수 있으므로 result에 mid 값을 저장하고, 간격을 더 줄일 수 있는 지 확인하기 위해 start를 mid + 1로 업데이트합니다.
  • 설치한 공유기 개수(count)가 설치해야 하는 공유기 개수(c)보다 작다면 공유기를 모두 설치하지 못했다는 의미이므로 간격을 줄여주어야 합니다. end를 mid로 업데이트합니다.

 

🌱 코드

  

    
    
    
    
  
# usr/bin/env python
# -*- coding: utf8 -*-
# boj 2110 공유기 설치

import sys
input = sys.stdin.readline

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

start,end = 1, position[n-1] - position[0]
result = 0

if c == 2:
    print(position[n - 1] - position[0])
else:
    while(start < end):
        mid = (start + end)//2

        # 첫번째 집에는 무조건 설치
        count = 1
        installed = position[0]

        for i in range(n):
            if position[i] - installed >= mid:
                count += 1
                installed = position[i]    # 공유기 설치
        if count >= c:
            result = mid
            start = mid + 1     # 간격 늘리기
        elif count < c:
            end = mid       # 간격 줄이기
    print(result)