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

Problem

랜선을 K개 가지고 있는데 각각을 일정한 수로 잘라 나누어진 값을 더했을때 N개가 되어야함.

Solution

1)K개의 리스트중 1~가장큰값을 이분탐색하여
2)주어진 랜선값들을 나누어 그 합을 계산하고
3)더 많이 잘랐으면 left값을 높여 잘려지는 수를 적게 해주고
3)반대면 right값을 낮추기

코드설명

1)lt=1, rt=max(arrList)로 설정
2)이분탐색 mid값을 for문으로 cnt계산하여 잘려지는 랜선값 구하기
3)랜선값이 N보다 많이 잘렸다!=즉 덜 잘려야하면 mid값을 높여야 하므로 lt+=1하기
4)반대면 rt+=1하기

※아래 부분은 랜선의 최대 길이를 구하는 부분이므로 만약에 랜선이 잘린값이 여러개 나온다면 최대값을 구해야하므로 아래와 같이 설정.

if cnt>=M :
     res=mid
     lt=mid+1

Python Code

import sys

N,M=map(int,sys.stdin.readline().split())
arrList=[]
for _ in range(N):
    tmp=int(sys.stdin.readline())
    arrList.append(tmp)

arrList.sort()

lt=1
rt=max(arrList)

maxValue=-1
res=0

while lt<=rt:
    cnt=0
    mid=(lt+rt)//2

    for x in arrList:
        cnt+=x//mid

    if cnt>=M :
        res=mid
        lt=mid+1

    else:
        rt=mid-1
print(res)