백준 1654(랜선 끊기) 비단뱀

https://www.acmicpc.net/problem/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일 때 검색을 중지합니다.