쉬운 문제로 생각했지만 문제 자체를 잘못 이해했다... 잘못 이해한 내용을 쓰는 건 불필요한 일일 것이다.
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))
'코드' 카테고리의 다른 글
The Grid Search (0) | 2021.10.28 |
---|---|
Non-Divisible Subset (0) | 2021.10.25 |
하노이의 탑 (0) | 2021.08.04 |
터렛 (0) | 2021.08.03 |
연역 가이드 (0) | 2021.05.22 |