[백준] 1654번 : 랜선 자르기 (파이썬)



문제


나의 답안

k,n=map(int,input().split()) #랜선의 개수, 필요한 랜선의 개수
lan=[]
for i in range(k):
    lan.append(int(input()))#랜선의 길이

#랜선의 최대 길이

mn,mx=1,max(lan)

while mn<=mx:
    cnt=0
    mid=(mn+mx)//2
    
    for i in lan:
        if i>=mid:
            cnt+=i//mid
    if cnt>=n:  #만들어야 될 랜선수보다 큰 경우
        mn=mid+1 #최소 길이를 증가
    else:   #만들어야 될 랜선 수보다 적은 경우
        mx=mid-1 #최대 길이를 감소
print(mx)

접근 방법

  • 나무 자르기 문제와 거의 동일하다
  • 랜선의 개수보다 많으면 랜선의 최소 길이를 증가시키고, 랜선의 수보다 작으면 최대 길이를 감소한다.

좋은 웹페이지 즐겨찾기