[백준 1654] 랜선 자르기

[백준 1654] 랜선 자르기

1654번: 랜선 자르기

편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

https://www.acmicpc.net/problem/1654

Tip

•

기존에 사용하던 재귀함수 대신 while문을 사용해서 더 간단하고 빠른 이진탐색 구현

풀이 소스 코드

import sys
si = sys.stdin.readline
k, n = map(int, si().split())
array = [int(si()) for _ in range(k)]
start = 1
end = max(array)
while start <= end:
mid = (start + end) // 2
cnt = 0
for i in array:
cnt += i // mid
if cnt >= n:
start = mid + 1
else:
end = mid - 1
print(end)
Python