[알고리즘]랜선 자르기

문제

엘리트 학원은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이 다. 선생님은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm 은 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)
편의를 위해 랜선을 자를때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수 길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

입력예제1

4 11
802
743
457
539

출력예제1

200

[내 코드]

def is_binary(a,N):
    start=1
    end=max(a)
    while start<=end:
        mid=(start+end)//2
        sum=0
        for i in range(len(a)):
            sum+=a[i]//mid
        if sum>=N:
            result=mid
            start=mid+1
        else:
            end=mid-1
    return result

K,N=map(int,input().split())
a=[]
for i in range(K):
    a.append(int(input()))
n=is_binary(a,N)
print(n)

1. 이분탐색 알고리즘을 이용한다.
2. a리스트의 값중 가장 큰 값을 end로 설정하고 이분탐색을 진행
3. a리스트에 있는 요소들을 각각 mid로 나눈 값을 sum에 더한다.
4. sum이 N값보다 크다->랜선길이가 최댓값이 아니다. 즉, 랜선을 필요한 수 보다 더 많이 짜름.
5. sum이 N값보다 작다->랜선이 필요한 갯수보다 적다.

[해설코드]

def Count(len):
	cnt=0
    for x in Line:
    	cnt+=(x//len)
    return cnt
k,n=map(int,input().split())
Line=[]
res=0
largest=0
for i in range(k):
	tmp=int(input())
    Line.append(tmp)
    largest=max(largest,tmp)
lt=1
rt=largest
while lt<=rt:
	mid=(lt+rt)//2
    if Count(mid)>=n:
    	res=mid
        lt=mid+1
    else:
    	rt=mid-1
print(res)