[BOJ/Python] 2110. 공유기 설치

이 문제 풀면서 궁금했던 점: 공유기 1개가 몇개까지 커버치는지가 궁금했는데 문제 방향이랑은 크게 상관이 없음
이분 탐색으로 풀어야겠다는 생각은 못하고 각 공유기의 지점을 포인터로 지정해야 하나 생각함 -> 근데 이래 버리면 포인터가 공유기 개수만큼 있어야 하니까 안됨 -> 완전 탐색으로 풀어야 하나 생각함 -> 시간이...?????????되나

➡ N = 200,000, C = 200,000일 때,
➡ 가능한 공유기 간 거리(gap)의 최대값은 1,000,000,000 (10억)
➡ 완전 탐색(O(N * max_gap))으로 해결하려면 최악의 경우 200,000 * 10^9 = 2 * 10^13

결론: 최대, 최소 거리 문제의 경우 시간복잡도를 계산해보고 완전 탐색 안될거 같으면 이진탐색으로 가자...

for gap in range(1, max_gap + 1):  # O(max_gap)
    count = 1
    prev = house_list[0]

    for i in range(1, N):  # O(N)
        if house_list[i] - prev >= gap:
            count += 1
            prev = house_list[i]

    if count >= C:
        best_gap = gap

 

 

유의: prev, cnt 변수 지정
공유기의 개수를 기반으로 두 공유기 사이의 최대 거리를 조절함

답안:

import sys

def solution(N, C, house_list):
    house_list.sort()  # 집 좌표 정렬
    left, right = 1, house_list[-1] - house_list[0]  # 최소 거리, 최대 거리
    answer = 0  # 최적의 거리

    while left <= right:
        mid = (left + right) // 2  # 중간값
        prev, cnt = house_list[0], 1  # 첫 번째 집에 공유기 설치,
        # 현재 설치한 공유기의 개수 cnt

        for i in range(1, N):
            if house_list[i] - prev >= mid:  # mid 이상의 거리 확보 시 공유기 설치
                cnt += 1
                prev = house_list[i] 
                # 마지막으로 공유기가 설치된 위치를 갱신함

        if cnt >= C:  # 설치된 공유기 개수가 기존에 받은 것보다 많거나 같으면
            answer = mid  # mid 값을 최적 거리 후보로 두고
            left = mid + 1 #거리를 늘려봄
        else:  # 공유기 개수가 부족하면 거리 줄이기
            right = mid - 1

    return answer  # 최적 거리 반환

# 입력 처리
input = sys.stdin.readline
N, C = map(int, input().split())
house_list = [int(input().strip()) for _ in range(N)]

# 결과 출력
print(solution(N, C, house_list))