공유기 설치

2021.05.17

공유기설치

Solution

가장 인접한 두 공유기 사이의 최대거리를 x라고 하겠습니다.

x의 최소값은 두 집이 인접할 때의 거리인 1이고, 최대값은 가장 오른쪽집 - 가장 왼쪽집이 됩니다. (1 <= x <= Xn - X1)

x의 값에 맞춰서 C개의 공유기를 N개의 집에 설치하는 것이 가능하다면(CanBuild라고 하겠습니다.) 해당 x는 정답의 후보군이 됩니다.

CanBuild 는 가장 왼쪽 집부터 하나씩 x이상의 거리를 두고 설치해보려 했을 때, C개 이상 설치할 수 있다면 True 가 됩니다.

완전탐색

x의 최솟값부터 최댓값까지 모두 탐색하여 가능한 x 중 최댓값을 구하는 방법이 있습니다. 하지만 이렇게되면 O(Xn * N) 정도 시간복잡도가 소요됩니다. Xn은 10억 이하인 수 이므로 매우 오래걸리게 되죠.

그럼 어떻게 해야할까요?

이진탐색

x가 a일 때 not CanBuild 이면 a+1일 때도 not CanBuild 인 것을 생각해볼 수 있습니다.

짧게 붙였을때도 설치할 수 없었는데 길게 붙이려고하면 설치할 수 없겠죠.

즉 x가 증가함에 따라 CanBuild 의 결과는 확인해보면,

O O O O O O ... O O X X X ... X X X (O는 True, X는 False)가 됩니다.

맨 왼쪽을 start로, 맨 오른쪽을 end로 잡고 이진탐색으로 문제를 해결할 수 있습니다.

start와 end의 핵심 기준은

• start : CanBuild 가 True 인 지점
• end : CanBuild 가 False 인 지점

입니다.

v1

정답의 후보군을 특정 구간의 모든 정수가 아니라 가능한 인접 거리 중에서 이진탐색하도록 했습니다. 실제로 두 집 사이의 인접거리여야 정답의 후보군이 될 수 있기 때문이죠.

또, C가 2 이면 end의 초기값에서 CanBuild가 True일 수 있습니다. 이 경우에는 end의 초기값이 정답이고 처음에 정의한 end의 기준에 부합하지 않게되므로 바로 end를 return하도록 구현하였습니다.

dist 리스트를 만드는 2중 for loop 에서 O(N*N)이 소요되게 되어 시간초과가 발생합니다.

def CanBuild(N, C, home, min_dist):
    cnt = 1
    tmp_dist = 0
    for i in range(1, N):
        tmp_dist += (home[i]-home[i-1])
        if tmp_dist >= min_dist:
            tmp_dist = 0
            cnt += 1
    if cnt >= C:
        return True
    else:
        return False

def solution(N, C, home):
    ret = None
    home.sort()
    dist = []
    for i in range(N):
        for j in range(i+1, N):
            if home[j]-home[i] not in dist:
                dist.append(home[j]-home[i])
    dist.sort()
    # Binary Search
    start = 0
    end = len(dist) - 1

    if CanBuild(N, C, home, dist[end]):           # OOOOOOO....OOOOO 인 경우
        return dist[end]

    while start + 1 < end:
        mid = (start + end) // 2
        if CanBuild(N, C, home, dist[mid]):
            start = mid
        else:
            end = mid

    return dist[start]

N, C = map(int, input().split())
home = [int(input()) for _ in range(N)]

print(solution(N, C, home))

v2

이진탐색을 할 때, O O O O O O ... O O X X X ... X X X 가 결과모음이라고 할 때,

O에서 X로 넘어가는 x값 (k라고 하겠습니다.) 에 주목해보겠습니다.

k 일때 설치가 가능하고 k+1 일때 설치가 불가능하다는 것은, k 일때는 딱 걸쳐서 설치할 수 있었던 집에 k+1 일때는 설치하지 못하게 됩니다.

따라서 dist 배열 꼭 실제 가능한 인접거리로 구성하지 않더라도 정답을 찾는데에는 문제가 되지 않습니다.

dist 배열을 아예 가능한 정수구간으로 구성하려 했습니다.

하지만 최악의 경우 10억개로 된 리스트가 만들어져 메모리 초과가 발생했습니다.

=> dist 배열 만드는 데 메모리초과
def CanBuild(N, C, home, min_dist):
    cnt = 1
    tmp_dist = 0
    for i in range(1, N):
        tmp_dist += (home[i]-home[i-1])
        if tmp_dist >= min_dist:
            tmp_dist = 0
            cnt += 1
    if cnt >= C:
        return True
    else:
        return False

def solution(N, C, home):
    ret = None
    home.sort()
    dist = [n for n in range(1, home[-1]-home[0])]

    # Binary Search
    start = 0
    end = len(dist) - 1

    if CanBuild(N, C, home, dist[end]):           # OOOOOOO....OOOOO 인 경우
        return dist[end]

    while start + 1 < end:
        mid = (start + end) // 2
        if CanBuild(N, C, home, dist[mid]):
            start = mid
        else:
            end = mid

    return dist[start]

N, C = map(int, input().split())
home = [int(input()) for _ in range(N)]

print(solution(N, C, home))

v3

dist 배열이 연속된 숫자라면 굳이 배열로 만들 필요가 없어 제거하여 통과했습니다.

def CanBuild(N, C, home, min_dist):
    cnt = 1
    tmp_dist = 0
    for i in range(1, N):
        tmp_dist += (home[i]-home[i-1])
        if tmp_dist >= min_dist:
            tmp_dist = 0
            cnt += 1
    if cnt >= C:
        return True
    else:
        return False

def solution(N, C, home):
    # Binary Search
    start = 1

    end = home[-1] - home[0]
    if CanBuild(N, C, home, end):           # OOOOOOO....OOOOO 인 경우
        return end

    while start + 1 < end:
        mid = (start + end) // 2
        if CanBuild(N, C, home, mid):
            start = mid
        else:
            end = mid

    return start

N, C = map(int, input().split())
home = [int(input()) for _ in range(N)]
home.sort()

print(solution(N, C, home))