백준 1654 [랜선 자르기] 파이썬

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

1654번: 랜선 자르기

처음 접근은 평균을 내고, 평균부터 시작해서 1씩 빼면서 N개를 만들 수 있는지 탐색하였다. 시간 초과가 발생하였다.

#백준 1654 랜선 자르기 시간초과 코드
K,N=map(int,input().split())
lans=[]
lans_sum=0
lans_avg=0
temp=0
for _ in range(K):
    lan=int(input())
    lans_sum+=lan
    lans.append(lan)
lans_avg=lans_sum//N
temp=lans_avg
while temp>0:
    cnt=0
    for lan in lans:
        cnt+=lan//temp
    if cnt>=N:
        answer=temp
        break
    temp-=1

print(answer)

어떻게 풀지를 생각하다가 이분 탐색을 사용하면, 탐색 수가 줄겠구나 라는 생각이 들어 이분 탐색으로 도전하였다.

#백준 1654 랜선 자르기
K,N=map(int,input().split())
lans=[]
lans_sum=0 # 랜선의 총합 
lans_end=0 # 탐색 끝 범위
lans_start=0 #탐색 시작 점위
temp=0 # 탐색 기준점 (중점)
answer=0 # 정답
for _ in range(K): #우선 리스트에 저장
    lan=int(input())
    lans_sum+=lan
    lans.append(lan)
lans_end=(lans_sum//N)+1 #끝점을 초기화

while True:
    cnt=0
    if lans_start==lans_end:
        break
    temp=(lans_end+lans_start)//2 #중점을 설정
    for lan in lans:
        cnt+=lan//temp
        if cnt>=N: # 개수가 N게 이상이면, 정답을 temp로 설정
            answer=temp
            lans_start=temp+1 # lans_start(temp+1)~lans_end의 범위를 탐색
            break
    if cnt<N: # 개수가 N개 이하이면
        lans_end=(temp) # # lans_start~lans_end(temp)의 범위를 탐색

print(answer)

K개의 단순합을 N으로 나눈 평균을 lans_end라고 했다.

초기 탐색 범위는 [0, lans_sum//N+1] 이고,

개수를 N개 이상 만들 수 있으면, 탐색 범위는 [temp+1,lans_end]

개수를 N개 미만으로 만들 수 있으면, 탐색 범위는 [lans_start,temp] 이다.

이분 탐색을 계속 하다, lans_start==lans_end 이면 탐색을 종료한다.