[백준] 1654. 랜선 자르기

문제

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

1654번: 랜선 자르기

 

설계

- 이분탐색

- 처음에는 2중 while문을 이용하여 전선의 개수를 카운트, 시간초과

- cnt += line // mid 를 이용하여 while문 대신 한번에 cnt 계산

- start = 1로 해야 cnt += line // mid 에서 mid가 0이 되지 않는다.

# 랜선 자르기

K, N = map(int, input().split())
arr = [int(input()) for _ in range(K)]

start, end = 1, max(arr)        # end : 한번에 최대한 크게 만들 수 있는 전선의 길이
answer = 0
while start <= end:
    mid = (start + end) // 2    # 최대 전선 길이
    cnt = 0

    for line in arr:
        cnt += line // mid		# 개수를 한번에 더해줌

    if cnt >= N:     # 필요한 전선 개수 이상 생산한 경우
        start = mid + 1
    else:
        end = mid - 1

print(end)