백준 2110번 공유기 설치

출처 : 2110번: 공유기 설치 (acmicpc.net)

2110번: 공유기 설치

---

공유기 설치 성공분류

시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율

2 초

128 MB

17953

7159

5270

42.432%

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

5 3 1 2 8 4 9

예제 출력 1 복사

3

힌트

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

---

[ 문제 설명 ]

 

이 문제를 풀 때는 기본적으로 이분 탐색의 개념은 안다는 전제하에 설명을 하겠다. 이분탐색의 개념을 모르신다면 제 블로그의 백준 1654번 - 랜선 자르기 (tistory.com)를 봐주시면 감사하겠습니다.

 

이분 탐색의 가장 중요한 점은 1654번 랜선 자르기에 빗대서 표현하면 잘라서 몇 개 나오는 토막처럼 비교할 target 설정을 어떻게 해야 하는지가 중요하다.

 

자세한 설명은 그림으로 설명하겠다.

 

그림 1 - 공유기 설치 설명

그림 2 - 공유기 설치

이런 식으로 이진 탐색해가는 것. 그림을 이해하고 코드 블록을 보시면 확실한 이해가 되실 것.

---

[ 코드 ]

 

import sys

n, c = map(int, sys.stdin.readline().split())

router = []

for j in range(n):
    j = int(input())
    router.append(j)

router.sort()
# print(router)
start = 1
end = router[-1] - router[0]
result = 0
while start <= end:
    # print("=====")
    gap_mid = (start + end) // 2  # mid 는 gap 을 의미 (간격 최소 예쌍값)
    # print("mid: ", mid)
    value = router[0]
    routerCount = 1
    for i in range(1, n):
        # print("router[i]:", router[i])
        if router[i] >= value + gap_mid:  # 간격 최소 예쌍값보다 작으면 안된다 -> 문제 조건에서 간격은 항상 최대로...때문에
            # print("router[i]:", router[i])
            value = router[i]
            routerCount += 1

    if routerCount >= c:  # c 개 이상의 공유기를 설치할 수 있는 경우
        start = gap_mid + 1
        result = gap_mid

    elif routerCount < c:
        # c 개 이상의 공유기를 설치할 수 없는 경우 -> 간격을 최대로 하고 찾다보면 공유기를 다 설치하지 못하는 경우 발생
        # print("count: ", count)
        end = gap_mid - 1  # 최대 간격을 줄여주자!
        # print("end:", end)

print(result)

이해가 안 가신다면 제가 #해둔 print부분을 지우시고 프린트 출력된 내용을 음미해가면서 이해해도 되실 수 있을 겁니다.

하나씩 지우면서 조금씩 풀어야 도움이 됩니다.

---

후기

 

블로그에서 포스팅하면서 누군가에게 설명하는 듯하게 포스팅하면

아무도 안 보더라도 내가 정말 더 깊은 이해가 된다는 걸 새삼 느끼고

복습도 돼서 정말 좋다.

시간이 좀 걸리는 게 흠..?