오랜만에 만나 날 당황시키는 이분탐색 (실버3)

#1654번 랜선 자르기 https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

 

이분탐색이란 눈치를 채고 바로 풀었다

 

틀린코드

K, N = map(int, input().split())
lans = [int(input()) for _ in range(K)]

start = 1
end = min(lans)
while start <= end:
    mid = (start + end)//2
    pivot = sum(map(lambda x: x//mid, lans))
    if pivot == N:
        print(mid)
        break
    elif pivot > N:
        start = mid + 1
    elif pivot < N:
        end = mid - 1

바로 틀리길래 뭘 잘못했나 싶었다.

 

문제점

1. end 초깃값을 최솟값으로 설정했다. 최댓값으로 설정해야 빠짐없이 탐색할 수 있다. 

2. 이진탐색 내부에서의 논리문제였는데, 위의 형태에서는 답이 출력되지 않는 경우가 생긴다.

때문에 if문의 구조를 변경해야한다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

정답코드

K, N = map(int, input().split())
lans = [int(input()) for _ in range(K)]

start = 1
end = max(lans)
while start <= end:
    mid = (start + end)//2
    pivot = sum(map(lambda x: x//mid, lans))
    if pivot >= N:
        start = mid + 1
    elif pivot < N:
        end = mid - 1
print(end)