백준 - 2110번 공유기 설치 python 문제풀이 [Hellfer]

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

2110번: 공유기 설치

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

난이도 - 골드 4

 

end = house[-1] - house[0]  # 가장 멀리 떨어진 두 집 사이의 거리

 

우리는 집들 사이의 최대 거리를 구하려고 하므로, 이 거리는 절대로 '집들 중 가장 멀리 떨어진 두 집 사이의 거리'를 

초과할 수 없습니다. 따라서 이 값을 초기 end 값으로 설정하는 것이 합리적입니다.

house [-1] - house [0]은 정렬된 집의 좌표 리스트에서 가장 마지막 집의 좌표에서 첫 번째 집의 좌표를 뺀 값

즉 '집들 중 가장 멀리 떨어진 두 집 사이의 거리'를 계산한 것입니다.

이렇게 설정함으로써 이분 탐색의 범위를 적절하게 설정할 수 있습니다. 

 

이 문제를 풀기 위해 이분 탐색을 사용하는 이유는, 가장 인접한 두 공유기 사이의 최대 거리를 구하는 것이 '최적화 문제'이기 때문입니다. 이런 문제는 보통 이분 탐색, 동적 프로그래밍, 그리디 알고리즘 등을 통해 해결할 수 있습니다.

그러나 이 문제의 경우, 동적 프로그래밍이나 그리디 알고리즘을 사용하는 것은 적절하지 않습니다. 문제의 조건이 

'가장 인접한 두 공유기 사이의 거리'를 최대화하는 것이기 때문에, 이를 만족시키는 '최적의 해'를 바로 찾는 것은 어렵습니다.

예를 들어, 그리디 알고리즘을 사용한다면, 각 단계에서 '가장 멀리 떨어진 집에 공유기를 설치하는 것이 최적인가?'라는 질문을 던져야 합니다. 

하지만 이 경우, 이전 단계에서 설치한 공유기의 위치에 따라 다음 단계에서의 최적의 해가 달라질 수 있습니다. 

따라서 그리디 알고리즘을 적용하는 것은 적절하지 않습니다.

이분 탐색은 이런 '최적화 문제'를 풀기에 적합한 알고리즘입니다. 가능한 '가장 인접한 두 공유기 사이의 거리'를 

모두 시도해 보면서, 이를 만족하는 공유기의 개수를 구하고, 이를 기반으로 최적의 해를 찾아냅니다. 

🔶문제풀이 - 이분 탐색을 이용한 풀이,  시간 복잡도 O(logN)

# 집의 개수(n)와 공유기의 개수(m)를 입력받습니다.
n, m = map(int, input().split())

# 각 집의 좌표를 저장할 리스트를 선언합니다.
house = []

# 각 집의 좌표를 입력받아 리스트에 추가합니다.
for _ in range(n):
    x = int(input())
    house.append(x)
    
# 집의 좌표를 오름차순으로 정렬합니다.
house.sort()

# 이분 탐색을 위한 시작점과 끝점을 설정합니다.
start = 1
end = house[-1] - house[0]  # 가장 멀리 떨어진 두 집 사이의 거리

# 결과값을 저장할 변수를 선언합니다.
result = 0

# 이분 탐색을 시작합니다.
while start <= end:
    # 중간점을 설정합니다.
    mid = (start + end) // 2
    
    # 첫 번째 집에 공유기를 설치합니다.
    old = house[0]
    count = 1  # 설치한 공유기의 개수
    
    # 두 번째 집부터 마지막 집까지 순회합니다.
    for i in range(1, len(house)):
        # 현재 집의 좌표가 이전에 설치한 공유기의 좌표 + 중간값 이상이면 공유기를 설치합니다.
        if house[i] >= old + mid:
            count += 1
            old = house[i]
    
    # 공유기를 m개 이상 설치할 수 있으면 거리를 증가시킵니다.
    if count >= m:
        start = mid + 1
        result = mid  # m개 이상의 공유기를 설치할 수 있는 경우 중 가장 큰 거리를 저장
    # 공유기를 m개 미만 설치하면 거리를 감소시킵니다.
    else:
        end = mid - 1
        
# 가장 인접한 두 공유기 사이의 최대 거리를 출력합니다.
print(result)

🔶 문제 이해하기

# 이분 탐색을 시작합니다.
while start <= end:
    # 중간점을 설정합니다.
    mid = (start + end) // 2
    
    # 첫 번째 집에 공유기를 설치합니다.
    old = house[0]
    count = 1  # 설치한 공유기의 개수
    
    # 두 번째 집부터 마지막 집까지 순회합니다.
    for i in range(1, len(house)):
        # 현재 집의 좌표가 이전에 설치한 공유기의 좌표 + 중간값 이상이면 공유기를 설치합니다.
        if house[i] >= old + mid:
            count += 1
            old = house[i]
    
    # 공유기를 m개 이상 설치할 수 있으면 거리를 증가시킵니다.
    if count >= m:
        start = mid + 1
        result = mid  # m개 이상의 공유기를 설치할 수 있는 경우 중 가장 큰 거리를 저장
    # 공유기를 m개 미만 설치하면 거리를 감소시킵니다.
    else:
        end = mid - 1
   
# 가장 인접한 두 공유기 사이의 최대 거리를 출력합니다.
print(result)

 

예를 들어, 집의 개수 N이 5개이고 공유기의 개수 C가 3개인 경우를 생각해 봅시다.

 

또한 각 집의 좌표가 다음과 같이 주어졌다고 가정하겠습니다: 1, 2, 8, 4, 9

1. 우선, 집의 좌표를 오름차순으로 정렬합니다: 1, 2, 4, 8, 9

2. 가능한 최소 거리(start)는 1, 최대 거리(end)는 9 - 1 = 8입니다.

3. 이분 탐색을 시작합니다. 처음 중간값(mid)은 (1 + 8) // 2 = 4입니다.

4. 첫 번째 집에는 무조건 공유기를 설치합니다. 그리고 나머지 집을 순회하면서 현재 집의 좌표가 이전에 공유기를 설치한 집의 좌표 + 중간값 보다 크거나 같은 집이 있으면 그 집에 공유기를 설치합니다.

5. 중간값이 4일 때, 공유기를 설치한 집의 좌표는 1, 4, 8입니다. 따라서 공유기의 개수는 3개이므로, 최소 거리(start)를 중간값 + 1인 5로 업데이트합니다.

6. 이제 중간값은 (5 + 8) // 2 = 6이 됩니다.

7. 중간값이 6일 때, 공유기를 설치한 집의 좌표는 1, 8입니다. 따라서 공유기의 개수는 2개이므로, 최대 거리(end)를 중간값 - 1인 5로 업데이트합니다.

8. 이제 중간값은 (5 + 5) // 2 = 5입니다.

9. 중간값이 5일 때, 공유기를 설치한 집의 좌표는 1, 8입니다. 따라서 공유기의 개수는 2개이므로, 최대 거리(end)를 중간값 - 1인 4로 업데이트합니다.

10. 이제 중간값은 (5 + 4) // 2 = 4입니다. 하지만 이전에 중간값이 4일 때 계산한 결과를 이미 알고 있으므로, 공유기의 개수는 3개입니다. 따라서 최소 거리(start)를 중간값 + 1인 5로 업데이트하려고 합니다.

11. 하지만 이 경우, 최소 거리가 최대 거리보다 크므로 while문이 종료됩니다.

12. 따라서, 가장 인접한 두 공유기 사이의 최대 거리는 4입니다.

이렇게 이분 탐색을 사용하면 원하는 조건을 만족하는 최적의 해를 효율적으로 찾을 수 있습니다.

 

🤗파이팅입니다~ 여러분!!🤗