BOJ1654 랜선 자르기

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

1654번: 랜선 자르기

 

난이도: 실버2

소요시간: 60분, 엣지케이스 관련 힌트 참고함

 

최대로 나올수 있는 값을 end로 정했다.

1~end를 이분탐색하여서 정답을 찾았다.

 

 

import sys

K,N = map(int,sys.stdin.readline().split())
end=0
cableList=[]
for _ in range(K):
    temp=int(sys.stdin.readline())
    cableList.append(temp)
    end+=temp

end = end//N
start=1
midList=[]
while start<=end:
    mid = (start+end)//2
    count=0

    for cable in cableList:
        count+=cable//mid
    if count >=N:
        start=mid+1
    else:
        end=mid-1
    midList.append([mid,count])

result=[]

for i in range(-(len(midList)),0):
    if midList[i][1] >=N:
        result.append(midList[i][0])


print(max(result))