[백준 2024/04/16] 2110번 공유기 설치

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

2110번: 공유기 설치

 

1. 접근 방법

이 문제는 처음에는 dfs로 접근했다가, 재귀 호출 recursion error가 발생해서 다르게 접근해야 했다.

 

백준 밑에 있는 이분 탐색이라는 힌트를 보게 되었고 이를 이용해서 문제를 해결하고자 하였다.

이분 탐색을 어떤 기준으로 해야할 지 고민하다가 아래 유튜브 영상을 보게 되었다.

https://www.youtube.com/watch?v=zjchexvpz5k&t=1872s

 

이 영상을 통해 이해하고 직접 코드를 짜서 이해하게 되었다.

 

 

처음에 시작은

left = 1

right = 9

mid = 5

로 시작한다.

 

mid값이 5일 때, 즉 5의 거리를 공유기 간의 최소한의 거리를 5를 유지하면서 c개의 공유기가 설치한 지 알아보아야 한다.

1에 가장 먼저 설치하고 난 후, 6 보다 크거나 같은 집이 있는지 확인한다. 8이 다음으로 가능한데, 만약 8에 공유기를 설치하였다고 할 때, 

 

동일하게 8에서부터 5의 거리만큼 떨어진 곳에 공유기 설치가 가능한지 알아보아야한다. 8에서 5만큼 떨어진 곳은 13이고 이는 최댓값인 9의 범위를 벗어나게 되므로, 불가능하다

따라서 mid값이 5로 공유기를 설치하는 것은 불가하다.

 

따라서 이분 탐색으로 다시 mid값을 계산해주어야 한다.

 

따라서 다음 값들은

left = 1

right = 4 (mid -1)

mid = 2

 

공유기 간의 최소 거리를 2로 유지하면서 설치하는 것이 가능한 지 확인을 다시 진행한다.

 

이를 반복하며, 최댓값을 알아낸다.

 

2. 코드

def available(m, i, house, c):
    count = 1
    for h in house:
        if h >= i + m:
            count += 1
            i = h
        if count >= c:
            break

    if count < c:
        return False

    return True


def binary_search(house, c):
    l = 0
    r = house[-1]
    current = 0
    while l <= r:
        m = (l + r) // 2

        if available(m, house[0], house, c):
            l = m + 1
            current = m
        else:
            r = m - 1

    return current


def main():
    n, c = map(int, input().split())

    house = []
    for _ in range(n):
        house.append(int(input()))
    house.sort()

    print(binary_search(house, c))


if __name__ == '__main__':
    main()