2022-08-16 @이영훈
접근방법
이진탐색 (binary search) 문제입니다. 케이블의 최대 개수가 1만개 입니다. 케이블의 길이를 1부터 랜선의 최대 길이 L까지 반복해야 합니다. 이 때 L이 1억이라고 했을 때, 계산량이 많아서 시간 초과가 예상됩니다. 따라서 이진탐색으로 O(logN) 으로 탐색 시간을 줄여야 합니다.
만들려고 했던 랜선의 개수가 나왔을 때 처리 로직은
•
시작값을 중앙값보다 하나 증가시킵니다
•
만약에 중앙값이 정답이라면 끝값(end)에서 다시 그 중앙값이 나와서 정답이 됩니다
•
반환을 끝값으로 해서 정답을 구합니다
파이썬 코드
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)
Python
복사