[python] 백준 2110 ::

by

(라우터 설치)

# 문제
도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

# 입력
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

# 출력
첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

설명

전체 코드

import sys

N, C = map(int, input().split())
houses = (int(sys.stdin.readline()) for _ in range(N))
houses.sort()

left, right = 1, houses(-1) - houses(0) # 최소 거리, 최대 거리
result = 0
while left <= right:
    mid = (left + right) // 2  # 중간 지점

    prev_house = houses(0)  # 이전 공유기가 설치된 집
    count = 1  # 설치한 공유기의 개수

    # 모든 집을 순회하면서 mid 거리 이상인 경우에만 공유기를 설치
    for i in range(1, len(houses)):
        if houses(i) - prev_house >= mid:
            prev_house = houses(i)
            count += 1

    # 공유기를 C개 이상 설치할 수 있는 경우, mid 값을 저장하고 더 큰 값으로 이동
    if count >= C:
        result = mid
        left = mid + 1
    # 공유기를 C개 이상 설치할 수 없는 경우, 더 작은 값으로 이동
    else:
        right = mid - 1

print(result)

0. 해결 방법

  • 이진 검색을 사용합니다.
  • 모든 집 사이의 최소 거리그리고 최대 거리의 합중거리보다 먼 집에서 라우터를 찾아 설치하십시오.
  • 설치된 라우터 수에 따라 중앙값을 조정하고 과정을 반복합니다.

1. 오름차순 정렬

houses.sort()
  • 이진 검색을 위해 오름차순으로 정렬합니다.
    (바이너리 검색은 오름차순 정렬이 더 편함)

2. 바이너리 검색을 위한 초기값 설정

left, right = 1, houses(-1) - houses(0) # 최소 거리, 최대 거리
  • 최소 거리(왼쪽): 1
  • 최대 거리(오른쪽): 좌표가 제일 큰 집 - 좌표가 제일 작은 집

3. 라우터를 설치하자

  • 첫 번째 집에 설치하여 시작하겠습니다.
    prev_house = houses(0)  # 이전 공유기가 설치된 집
    count = 1  # 설치한 공유기의 개수

  • 설치된 홈에서 절반 이상 떨어져 있는 홈을 찾으면 해당 홈에도 라우터를 설치하십시오.
  • 공유기 설치 직전 집값 저장 prev_house에서 현재 설치된 집으로 값을 변경합니다.
  • 라우터를 설치했기 때문에 count 값도 +1
    # 모든 집을 순회하면서 mid 거리 이상인 경우에만 공유기를 설치
    for i in range(1, len(houses)):
        if houses(i) - prev_house >= mid:
            prev_house = houses(i)
            count += 1

4. 현재 사례에 설치된 라우터 수와 문제에서 제안한 라우터 수를 비교합니다.

  • 설치된 라우터의 수가 정확하거나 너무 많은 경우 라우터 간 거리 늘리기주다.
    그런 다음 더 적은 수의 집에서 끝납니다!
  • 그룹화 이유는 딱 맞는 커버리지의 경우와 커버리지가 너무 많은 경우
    지금 딱 맞으면 거리두기를 늘릴 수 있어서 좋을 것 같아요!
  • 그리고 이것이 답이 될 수 있습니다 result그걸 써
    (검색이 완료되면, 즉 while 루프가 끝난 후, result인쇄됨)
    # 공유기를 C개 이상 설치할 수 있는 경우, mid 값을 저장하고 더 큰 값으로 이동
    if count >= C:
        result = mid
        left = mid + 1

  • 라우터 수가 적을 경우 라우터 사이의 거리를 단축주다.
    그러면 더 많은 집이 덮일 것입니다!
    # 공유기를 C개 이상 설치할 수 없는 경우, 더 작은 값으로 이동
    else:
        right = mid - 1

그만~!

'추천 관련글,