[이분검색]랜선자르기

문제설명

엘리트 학원은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이 다. 선생님은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm 은 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)

문제해결 아이디어

• 토막낼 랜선의 최대 길이는 arr중 가장 짧은 랜선이다=max(arr)
• 0~max(arr)중 n개 이상의 토막을 낼 수 있는 최대길이를 구한다
• 토막낸 랜선의 갯수를 구하는 함수 Count()를 따로 정의한다

코드

import sys 

base='/Users/leesh970930/Desktop/pythonalgorithm_formac/섹션 4/'
sys.stdin=open(base+'2. 랜선자르기/in1.txt', "r")

def Count(len):
    cnt=0 #len으로 전체 랜선 k개를 토막냈을 경우 랜선의 갯수
    for i in arr:
        cnt+=(i//len)
        
    return cnt
    
k,n=map(int,input().split())
arr=[]
for _ in range(k):
    arr.append(int(input()))

largest=max(arr) #랜선이 아무리 길어도 가장 긴 랜선을 넘어가진 않음
lt=0
rt=largest
res=0 #토막낸 랜선의 길이

while lt<=rt:
    mid=(lt+rt)//2
    if Count(mid)>=n:
        res=mid 
        lt=mid+1
    else:
        rt=mid-1
print(res)