[WEEK02/DAY02] 백준 문제 : 공유기 설치

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

2110번: 공유기 설치

 

문제 해석 :

일직선 상에 놓여 있는 집 N개에 C개의 공유기를 설치할 때, 인접한 두 공유기 사이의 최대 거리를 구하는 문제이다.

 

즉 주어진 개수의 공유기를 모두 설치하면서도 공유기끼리 최대한 붙어있지 않게... 최대한 사이가 멀어지도록 해야 하는 것이다.

 

일일히 모든 집에 하나씩 놓아보면서 완전 탐색을 하다가는 시간 초과가 날 것이 뻔하다. 집의 개수 N의 범위는 (2 ≤ N ≤ 200,000)이고, 공유기 C는 (2 ≤ C ≤ N), 집의 좌표 xi는 (0 ≤ xi ≤ 1,000,000,000)의 범위를 가지고 있기 때문이다.

 

그래서 이분 탐색을 통해 O(logN)의 시간복잡도를 가지도록 해야겠다는 생각은 했는데, 도대체 어떤 값을 기준으로 이분 탐색을 해야 하는지 감을 잡기가 쉽지 않았다.

 

 

접근 :

우선은 시간을 고려하지 않고 답을 찾아낼 수 있는 방법을 생각해 보았다.

 

내가 처음 생각했던 방법은 우선 주어진 집들의 양 끝(left, right)에 공유기를 놓고, 중간값을 (left+right)//2로 잡아서 중간값에 제일 가까운 집을 찾는 것이었다. 그런 식으로 반복하다보면 공유기끼리 최대한 멀어지게 놓을 수 있지 않을까 생각했는데, 결론적으로는 아주 틀린 생각이었다.

당장 공유기 4개를 놓는다고 가정했을 때 양 끝에 하나씩을 놓는다고 치면 나머지 두개를 균등한 간격으로 놓아야 최대거리를 만들 수 있을텐데, 위의 방법대로 하면 중앙에 근접한 곳에 놓게 되므로 최대거리와는 거리가 멀어지게 된다.

집1	집2	집3	집4	집5
1	4	6	7	10

위의 표처럼 집이 5개 놓여있을 때 공유기 4개를 1, 4, 7, 10에 놓으면 최대거리를 3으로 유지할 수 있지만
1, 10에 먼저 놓고 중간인 6에 놓아버리게 되면 1, 4, 6, 10에 놓이게 되고 최대거리는 2가 되어버린다.
따라서 위의 방법은 틀린 방법이다.

그래서 결국 다른 사람이 푼 내용을 참고했는데, 매개변수를 공유기 사이의 거리로 놓아야 한다는 사실을 알게 되었다.

 

우선 최대 거리를 양 끝 집 사이의 거리로 잡고, 최소 거리는 1로 잡는다.

그리고 거리의 중간값을 구하며 범위를 좁혀 나가야 한다.

 

이분 탐색에서 앞쪽 범위를 선택할지, 뒷쪽 범위를 선택할지 결정할 때는 올바른 기준을 잡는 것이 중요하다.

여기서는 해당 중간값 거리마다 공유기를 설치했을 때, 주어진 공유기 수보다 많은지 적은지를 기준으로 잡았다.

주어진 공유기 수보다 많이 설치할 수 있다면 -> 거리가 너무 좁은 것이므로 더 넓혀 볼 수 있고 (min 값에 mid 대입하여 기준값 위를 탐색)

주어진 공유기 수보다 부족하게 설치했다면 -> 거리가 너무 넓은 것이므로 더 좁히면 된다. (max값에 mid 대입하여 기준값 아래를 탐색)

 

 

 

 

 

코드가 많이 부족하지만, 같은 어려움을 겪고 있는 분들께 도움이 되길 바라며 공유한다.

import sys

def main() -> None:
    n, c = sys.stdin.readline().split()
    n, c = int(n), int(c)
    x = [int(sys.stdin.readline().strip()) for _ in range(n)]
    x.sort()

    if c == 2:
        print(x[-1] - x[0])
        return

    result = 0

    max_len = x[-1] - x[0]
    min_len = 1

    while max_len >= min_len:
        mid_len = (max_len+min_len)//2
        house = x[0]
        count = 1
        for i in range(1, len(x)):
            if x[i] - house >= mid_len:
                count += 1
                house = x[i]
        if count >= c:
            result = mid_len
            min_len = mid_len+1
        else:
            max_len = mid_len-1
    
    print(result)
    return


main()

 

 

알고리즘 분류 : 이분 탐색, 매개변수 탐색