[Python] 백준 - 1654번 랜선 자르기(Binary Search)

◈ 오류 정정 및 피드백 환영

1654번: 랜선 자르기

---

🔎문제 분석

만들 수 있는 랜선은 이미 가지고 있는 랜선의 길이를 넘을 수 없다.

따라서 1부터 기존 랜선의 최댓값에 이르는 범위를 탐색하며 정답을 찾으면 된다.

완전탐색으로는 시간 초과가 발생하기 때문에 이분탐색(Binary Search)으로 접근하면 된다.

 

만들어 낸 랜선의 개수가 n보다 크면 랜선 길이가 너무 짧은 것이므로 탐색 범위를 넓히면 되고, n보다 작으면 랜선 길이가 너무 긴 것이므로 탐색 범위를 좁히면 된다.

if cnt > n:
    l = mid+1
else:
    r = mid-1

랜선 개수가 정확히 n일지라도 구해야 하는 것은 랜선의 최대 길이이기 때문에 탐색을 멈춰서는 안 된다.

탐색 범위를 넓혀 더 긴 랜선 길이로도 조건을 만족하는지 확인해야 한다.

if cnt >= n:
    l = mid+1
else:
    r = mid-1

탐색 범위를 지나치게 넓히거나 좁혀서 시작점이 종료점보다 커지면 탐색을 종료한다.

while l<=r:

🤦‍♀️유의 사항

mid값을 리턴하고 싶다면 mid가 아닌 업데이트한 l과 r로 새로 계산한 mid를 리턴해야 한다.

애초에 종료된 시점에서 r이나 새로 계산한 mid나 값이 동일하기 때문에 r를 그대로 리턴하는 편이 낫다.

---

import sys
input = sys.stdin.readline
k, n = map(int, input().split())
a = [int(input().strip()) for _ in range(k)]

l = 1
r = max(a)
while l<=r:
    mid = (l+r)//2
    cnt = sum(map(lambda x: x//mid ,a))
    if cnt >= n:
        l = mid+1
    else:
        r = mid-1
print(r)