파이썬 백준 1654번: 랜선 자르기

문제 

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

1654번: 랜선 자르기

 

 

풀이

적절한 값을 찾을때까지 이진 탐색을 수행하여 랜선의 최대 길이를 반복해서 조정하면 된다

큰 탐색범위를 보면 가장 먼저 이진탐색을 떠올려야한다!

import sys
K,N =map(int,sys.stdin.readline().split(' '))
LAN=[]
for _ in range(K) :
    LAN.append(int(sys.stdin.readline()))
start=1
end=max(LAN)
while(start<=end): #이진탐색
    mid=(start+end)//2
    result=0
    for i in LAN:
        result+=(i//mid)
    if result>=N:
        start=mid+1
    else :
        end=mid-1
print(end)

 

😎주의

파이썬의 몫 연산자 //를 사용해야함

마지막에 start가 아닌 end를 출력해야함(start가 end보다 커졌을때 이진탐색을 종료하기때문)