BOJ1654 랜선 자르기

윤재에요 2023. 3. 20. 18:39

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

1654번: 랜선 자르기

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그

www.acmicpc.net

난이도: 실버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))