[백준] 2110번 공유기(파라메트릭 서치)(Python - 파이썬)

백준 2110번 문제입니다. (solved.ac)기준 골드 5 문제입니다.

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

2110번: 공유기 설치

힌트 : 공유기를 1, 4, 8 또는 1, 4, 9에 설치하면 가장 인접한 두 공유기 사이의 거리는 3이고, 이 거리보다 크게 공유기를 3개 설치할 수 없다.

 n개의 집에 c개의 공유기를 설치해야하는데 설치된 공유기들 중 가장 인접한 두 공유기 사이의 거리가 최댓값일 때를 찾고 그 길이를 출력하는 문제입니다.

 파라메트릭 서치를 이용하여 가장 인접한 공유기 사이의 최소거리(mid)를 구하도록 접근하였습니다. 가장 인접한 공유기 사이의  현재 집의 위치(처음 집의 위치는 house[0])에서 공유기 사이의 최소 거리(mid)를 더하여준 것이 다음 집의 위치보다 작거나 같다면 공유기 사이의 최소거리보다 다음 집이 멀리 있다는 소리이기 때문에 다음 집에 공유기를 설치해주고 다시 그 설치한 위치부터 탐색을 시작하였습니다. 만약 현재 집의 위치에서 공유기 사이의 최소 거리(mid)를 더한 것보다 다음 집의 위치가 작다면 다음 집의 위치가 공유기 사이의 최소 거리(mid)보다 가깝다는 소리이기 때문에 설치를 하지 않고 그다음 집과의 거리를 확인하게 됩니다.

---

 예제 1번으로 예시를 들자면 집은 (1, 2, 4, 8, 9)에 있고 공유기는 총 3대 설치해야합니다.

처음 탐색 간 공유기 사이의 최소 거리(mid)는 공유기 사이의 가능한 최소거리(start)(처음엔 1입니다. 0은 공유기가 겹친다는 뜻)과 공유기 사이의 가능한 최대 거리(end)(공유기의 좌표가 1,2,4,8,9 이기 때문에 가능한 최대 거리는 8입니다. (9-1))의 중간 값인 1+8 // 2 = 4에서부터  탐색을 시작합니다.

 공유기 사이의 최소거리가 4이기 때문에 1(처음 집의 위치/ house[0]에서 탐색을 시작하고(count = 1, 공유기를 시작점에 설치하고 탐색을 시작하니까) 2에 있는 집(house[1])은 1에 있는 집에서 최소거리인 4를 더한 것보다 작기 때문에 스킵, 4에 있는 집(house[2])또한 1에 있는 집에서 최소거리 4를 더한 것 보다 작기 때문에 스킵, 그 다음에 있는 8에 있는 집(house[3])은 1에 있는 집에서 최소거리인 4를 더한 것 보다 크기 때문에 공유기를 설치(count += 1, count = 2)합니다. 8에 있는 집(house[3])공유기를 설치하였기 때문에 8에 있는 집(house[3])에서 탐색을 시작합니다. 8에 있는 집(house[3])에서 최소거리인 4를 더한 값보다 다음 집인 9에 있는 집(house[4])이 더 작기 때문에 설치를 하지 않습니다. 9에 있는 집(house[4])이 마지막 집이어서 설치를 그만두고 설치해야 할 공유기의 수(c = 3) 보다 설치한 공유기의 수(count = 2)가 더 작기 때문의 공유기 사이의 최소거리를(mid)를 줄여 공유기를 더 설치해야 하기 때문에 줄여준 후(end = mid -1) 위의 과정을 start <= end 동안 반복하면 원하는 조건에 가장 알맞은 값(공유기를 3개 설치하고 인접한 공유기 사이의 거리가 최대가 될 때)을 구할 수 있게 됩니다.

정답 코드

# 2110번 공유기 설치

import sys
# 집의 수(n) 공유기의 수(c)를 입력 받음
n, c = map(int, sys.stdin.readline().rstrip().split())


router = []
# 집의 위치 좌표를 입력 받음
for _ in range(n):
    router.append(int(sys.stdin.readline().rstrip()))

# 파라메트릭 서치를 이용하기 위하여 오름차순으로 정렬
router.sort()

# 공유기 사이의 최소 거리
start = 1
# 공유기 사이의 최대 거리
# 가장 멀리떨어져 있는 집 사이의 거리가
# 공유기 사이의 최대 거리
end = max(router) - 1
# 결과를 담을 변수
result = 0


while (start <= end) :

    # mid는 가장 인접한 두 공유기 사이의 거리(공유기 사이의 최소거리)
    mid = (start+end) // 2
    # 집의 첫번째 위치에서 부터 탐색 시작
    cur = router[0]
    # 첫번째 위치에 공유기를 설치하고 탐색하기 때문에 count는 1 부터 시작
    count = 1

    # 현재위치(cur)에서 공유기 사이의 최소거리(mid)를 더한 값이 다음 집 위치 보다 작다면
    # 다음 집에 공유기를 설치!(공유기를 설치했기때문에 count += 1)
    # cur도 그 위지(routher[i]) 설정
    for i in range(1, len(router)) :
        if cur + mid <= router[i]:
            cur = router[i]
            count += 1

    # 공유기의 개수(c)보다 설치한 공유기의 개수(count)가 더 적으면
    # 공유기 사이의 거리를 줄여 공유기를 더 설치해야하므로
    # end = mid - 1을 해주어 다음 mid값을 줄이고 다시 탐색
    if count < c :
        end = mid - 1
    # result에 mid값을 먼저 넣어줌.
    # start <= end 동안 탐색하면서 갱신되고
    # 결국 가장 조건에 부합하는 값이 result에 들어가게됨(파라메트릭 서치)
    # 공유기의 개수(c)보다 설치한 공유기의 개수(count)가 크거나 같다면
    # 공유기 사이의 거리를 늘려 공유기를 덜 설치해야하므로
    # start = mid + 1을 해주어 다음 mid값을 늘리고 다시 탐색
    else :
        result = mid
        start = mid + 1

print(result)

비슷한 유형의 문제들

[백준] 2805번 나무 자르기(파라메트릭 서치(Python)

[백준] 2805번 나무 자르기(파라메트릭 서치(Python)

[백준] 1654번 랜선 자르기(파라메트릭 서치)(Python)

[백준] 1654번 랜선 자르기(파라메트릭 서치)(Python)

[백준] 2512번 예산(파라메트릭 서치)(Python)

[백준] 2512번 예산(파라메트릭 써치)(Python)