문제풀이

[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)}")