알고리즘 - Python / 백준 - 2110번 : 공유기 설치

2110번: 공유기 설치 (acmicpc.net)

2110번: 공유기 설치

 

---

풀이

• 수직선 상에 존재하는 집들의 좌표가 주어지고 , 집에 공유기를 k개 설치할 때 , 인접한 공유기끼리의 거리들 중 최솟값이 최대가 되도록 배치하는 문제다.
• 어떠한 범위를 k개로 잘라 , 자른 부분의 최솟값이 가장 커지려면 최대한 고르게 분배해야 한다는 아이디어를 통해 문제를 이해하였다.
• 예를 들어 9cm의 나뭇가지를 3개로 나눌 때 , 가장 작은 길이가 가장 큰 경우는 3등분 하여 3cm로 나누는 경우 일 것이다.
• 위의 나뭇가지 경우와 이번 문제의 다른 점은 자를 수 있는 곳이 한정되어 있다는 것이다.
• 이번 문제는 나뭇가지가 9cm 일 때 , 세 번 자르지만 자를 수 있는 곳은 나뭇가지 한쪽 끝에서 1cm , 3cm, 7cm, 8cm 만 자를 수 있다 이런 스타일의 문제다.
• 그렇다면 문제를 푸는 핵심 포인트는 바로 어떻게 해야 고르게 자를 수 있느냐 이다.
• 즉 자르는 길이를 어떻게 정해야 하는지가 핵심이다.
• 집 좌표의 길이가 0 ~ 10억 이기 떄문에 자르는 길이를 1부터 10억까지 다 해볼 수는 없다.
• 따라서 이분탐색을 활용하여 적절한 범위 안에서 조건을 만족하는 자르는 길이를 찾을 수 있다.
• 예를 들어 1 2 4 8 9 의 경우 , 자르는 길이는 최대 8 , 최소 1 이다.
• 즉 1 ~ 8 사이를 이분 탐색하며 자르는 길이를 정해주고 , 그 자르는 길이로 잘랐더니 공유기 수를 만족한다 하면 정답이 될 수 있는 것이다.
• 공유기 수를 만족하는지 체크해 주기 위해 첫째 집부터 출발하여 , [ 집 위치 + 자르는 길이 <= 공유기 설치할 집 위치 ] 인지 체크하며 , 만족하면 집 위치를 업데이트한다.
• 이분 탐색은 원하는 값을 찾으면 ( 이 경우 , 해당 공유기 수로 딱 알맞게 설치 가능한 경우 ) 멈추지만 , 문제에서는 최댓값을 찾아야 하기 때문에 멈추지 않고 끝까지 실행한다.
• 1 2 4 8 9 의 경우 ( 공유기 개수 3 ) , 자르는 길이 = 2 로 실행하면 아래 코드에서는 1 4 8 로 끝내버린다.
• 위의 경우는 우리가 찾는 최댓값이 아니기 때문에 끝까지 체크해서 찾아 주어야 한다.
• 이는 문제의 경우에 따라 정답이 정해져 있다는 결정론적 풀이로 이해할 수 있다.  

 

import sys
n,k = map(int , sys.stdin.readline().split(" "))
c = []; way = [0]
for _ in range(n):
    c.append(int(sys.stdin.readline()))
c.sort()
real_ans = 0
if k == 2:
    print(c[-1]-c[0])
else:
    way_start = 1
    way_end = c[-1] - c[0]
    while way_start <= way_end:
        start = c[0]
        way = (way_end + way_start) // 2
        ans = 1
        for i in range(1,len(c)):
            if c[i] - start >= way:
                start = c[i]
                ans += 1
        if ans >= k:
            real_ans = way
            way_start = way + 1
        elif ans < k:
            way_end = way - 1
    print(real_ans)

---