[알고리즘] 백준 1654번 랜선 자르기 python. binary search
🎭

[알고리즘] 백준 1654번 랜선 자르기 python. binary search

Created
2022/08/16
Tags
Algorithm
Python
Binary Search
 
2022-08-16 @이영훈
 
 

접근방법

이진탐색 (binary search) 문제입니다. 케이블의 최대 개수가 1만개 입니다. 케이블의 길이를 1부터 랜선의 최대 길이 L까지 반복해야 합니다. 이 때 L이 1억이라고 했을 때, 계산량이 많아서 시간 초과가 예상됩니다. 따라서 이진탐색으로 O(logN) 으로 탐색 시간을 줄여야 합니다.
 
만들려고 했던 랜선의 개수가 나왔을 때 처리 로직은
  • 시작값을 중앙값보다 하나 증가시킵니다
  • 만약에 중앙값이 정답이라면 끝값(end)에서 다시 그 중앙값이 나와서 정답이 됩니다
  • 반환을 끝값으로 해서 정답을 구합니다
 
 

파이썬 코드

Python
import sys

input = sys.stdin.readline

k, n = map(int, input().split())

cables = []
for _ in range(k):
    cables.append(int(input()))

start = 1
end = max(cables)

while start <= end:
    mid = (start + end) // 2

    count = 0
    for cable in cables:
        count += (cable // mid)

    if count >= n:
        start = mid + 1
    else:
        end = mid - 1

print(end)