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

 

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

쉬운 문제로 생각했지만 문제 자체를 잘못 이해했다... 잘못 이해한 내용을 쓰는 건 불필요한 일일 것이다. 

 

0,1개의 공유기는 조건에 없다. 2개의 공유기는 무조건 양극단에 배치된다. 그래야 문제의 조건대로 "가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다"를 만족할 수 있다. 3개의 공유기는 예제를 살펴보자.

 

3개의 공유기를 수평선 위치한 집에 설치한다고 하자.

[1] [2] [4] [8] [9]

 

3개의 공유기 간의 거리가 비슷하게 배치하는 방법은 1,4,8일 것이다. 1,4,9는 일종의 함정이다... 따라서 답은 3이 된다. 

 

이 문제에 실패한 이유는 다음과 같다. 첫째 해석의 실패, 둘째 이진 탐색으로 얻은 값을 맹신한 점이다. 문제에는 "가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성"하라는 조건이 있다. 따라서 탐색으로 적당한 공유기 거리를 얻었다고 해도, 허용 범위를 벗어날 때까지 값을 증가시켜 검색해야 한다.

 

 

import sys


def put_wifi(houses, length):
    last_house = houses[0]
    count = 1
    ans = float('inf')
    for house in houses[1:]:
        distance = house - last_house
        if distance >= length:
            last_house = house
            count += 1
            ans = min(distance, ans)

    return count


def sol(houses, wifi_count):
    houses = sorted(houses)
    min_length = 1
    max_length = houses[-1] - houses[0]
    prev_length = None

    # 이분 탐색해서 적당한 값 범위를 찾는다
    while True:
        length = (min_length + max_length) // 2
        count = put_wifi(houses, length)

        if count == wifi_count:
            break
        elif prev_length == length:
            break
        elif count < wifi_count:
            max_length = length
        else:
            assert count > wifi_count

            min_length = length

        prev_length = length

    # 공유기 개수가 불변하는 최대 범위를 찾기 위해 1씩 증가시켜 나간다
    while True:
        count = put_wifi(houses, length + 1)
        if count == wifi_count:
            length += 1
        else:
            return length

    assert False


houses = 0,1,2,3,4
assert 1 == sol(houses,6)

houses = 0, 34, 39, 41, 10, 11, 12, 44, 50, 31
assert 9 == sol(houses,5)

houses=1,3,4,7,8,9,10
assert 9 == sol(houses,2)

houses=1,2,8,4,9
assert 3 == sol(houses,3)

houses=1,4,6
assert 2 == sol(houses,3)

houses=1,7,8,9,10
assert 3 == sol(houses,3)

houses=1,3,7,8
assert 2 == sol(houses,3)

houses=1,4
assert 2 == sol(houses,2)


count, wifi = map(int,sys.stdin.readline().split())
houses = []
for _ in range(count):
    v = int(sys.stdin.readline().strip())
    houses.append(v)

answer = sol(houses, wifi)
sys.stdout.write(str(answer))