문제풀이
[PY] 2110 : 공유기 설치
pwerty
2025. 3. 24. 11:16
https://www.acmicpc.net/problem/2110
파일럿 코의 도움을 좀 받아버렸다.
직접 도움을 받기보단 가능한 적은 범위의 힌트를 받으려 했지만 끝판에 시간 초과가 나서 많은 내용을 눈물을 머금고 정리를 해야했다.
import sys
fieldCnt, routerCnt = list(map(int, sys.stdin.readline().strip().split()))
field = []
for i in range(fieldCnt):
field.append(int(sys.stdin.readline()))
field.sort()
start = 1
end = field[-1] - field[0]
while start <= end:
mid = (start + end) // 2
installedCnt = 1
lastInstalled = field[i]
for i in range(1, len(field)):
if field[i] - lastInstalled >= mid:
installedCnt += 1
lastInstalled = field[i]
if installedCnt >= routerCnt:
result = mid
start = mid + 1
else:
end = mid - 1
print(f"최적 거리: {result}")
기존의 코드
import sys
fieldCnt, routerCnt = list(map(int, sys.stdin.readline().strip().split()))
field = []
for i in range(fieldCnt):
field.append(int(sys.stdin.readline()))
field.sort()
minPos = field[0]
maxPos = field[len(field) - 1] - minPos
def isInstallAble(distance):
installed = 1
lastVisited = field[0]
for i in range(1, len(field)):
if(field[i] - lastVisited >= distance):
lastVisited = field[i]
installed += 1
if(installed == routerCnt):
return True
return False
def binarySearch(start, end):
result = 0
areFound = False
while (start <= end):
mid = (start + end) // 2
if isInstallAble(mid) is True:
result = mid
start = mid + 1
else:
end = mid - 1
return result
print(f"{binarySearch(1, maxPos)}")