[백준/파이썬] 2110

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

골드 4 공유기 설치

💫 알고리즘

이분 탐색 Binary Search

정렬된 데이터에서 특정 값을 빠르게 찾는 알고리즘

탐색 범위를 절반으로 줄여가며 중간값(mid)과 목표값을 비교하여 start 또는 end를 조정

목표값을 찾거나 탐색 범위가 끝날 때까지 반복

---

💡 풀이방향

🐢 이분 탐색과 그리디 알고리즘을 활용한 공유기 설치

1️⃣ N개의 집이 수직선 상 위치, 각 집의 좌표는 서로 다름

2️⃣ C개의 공유기를 가장 인접한 두 공유기 사이의 거리를 최대로 하여 배치

 

이분 탐색을 활용한 거리 최적화

3️⃣ 집 좌표 정렬: 작은 값부터 큰 값으로 순서대로 정렬

4️⃣ 이분 탐색 범위 설정

최소 거리 = 1 ; 가장 가까운 두 집 사이 최소 가능 거리

최대 거리 = x[-1] - x[0] ; 가장 먼 두 집 사이 거리

5️⃣ 이분 탐색

중간값 mid를 공유기 간 거리로 설정

mid 거리로 공유기 C개를 배치할 수 있는지 확인

# 배치할 수 있다면 start를 증가 (mid + 1)

# 배치할 수 없다면 end를 감소 (mid - 1)

가장 큰 mid 값을 정답으로 저장

---

🌟 코드 구현 + 👀 풀이

[전체 코드]

import sys
input = sys.stdin.readline

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

def bin_search(x, start, end):
    while start <= end:
        mid = (start + end) // 2
        current = x[0]
        count = 1

        for i in range(1, N):
            if x[i] - current >= mid:
                count += 1
                current = x[i]

        if count >= C:
            global result
            result = mid
            start = mid + 1
        else:
            end = mid - 1

start = 1
end = x[-1] - x[0]
result = 0

bin_search(x, start, end)
print(result)

 

이분 탐색 함수 bin_search

def bin_search(x, start, end):
    while start <= end:
        mid = (start + end) // 2   # 후보 최소 거리(mid)를 결정
        current = x[0]             # 첫 번째 집에 공유기 설치 (첫 설치 위치)
        count = 1                  # 이미 첫 집에 공유기를 설치했으므로 1로 초기화

        for i in range(1, N):
            # 현재 집과 이전에 설치된 공유기 사이의 거리가 mid 이상이면 공유기 설치
            if x[i] - current >= mid:
                count += 1
                current = x[i]   # 새로운 공유기 설치 위치로 갱신

        # 만약 공유기를 C개 이상 설치할 수 있다면
        if count >= C:
            global result
            result = mid         # 현재 후보(mid)를 결과로 저장
            start = mid + 1      # 더 큰 거리로 시도하기 위해 start 갱신
        # 공유기를 C개 설치할 수 없다면
        else:
            end = mid - 1        # 후보 거리 mid가 너무 크다는 뜻이므로 end = mid - 1로

 

이분 탐색 범위 초기화 및 함수 호출

start = 1
end = x[-1] - x[0]
result = 0

bin_search(x, start, end)
print(result)

start = 1

공유기 간 최소 거리; 서로 다 다른 좌표이므로

end = x[-1] - x[0]

가장 먼 두 집 사이 거리로 최대 후보값 설정

bin_search(x, start, end)

이분 탐색 함수 호출