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

이분 탐색 문제

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

---

💡 풀이코드 (성공)

import sys 
K, N = map(int, sys.stdin.readline().split())
lans = []
for _ in range(K):
    lan = int(sys.stdin.readline())
    lans.append(lan)

def binary_search(K, N, lans):
    start = 1
    end = max(lans)
    answer = 0

    while start <= end: # 0 1
        mid = (start + end) // 2

        cnt = 0
        for lan in lans:
            cnt += (lan // mid ) # ZeroDivisionError

        if cnt >= N:
            start = mid + 1 
            answer = mid 
        else:
            end = mid - 1
    return answer 

print(binary_search(K, N, lans))

 

1. 초기화

mid = 자를 랜선의 길이

mid가 자를 랜선의 길이를 의미하므로 자를 수 있는 랜선의 범위는 1 <= x <= max(lens)이다.

start = 1 # 자를 수 있는 랜선의 최소 길이
end = max(lans) # 자를 수 있는 랜선의 최대 길이

 

 

2. 디버깅 - ZeroDivisonError 해결

초기에 start = 0으로 설정해주었더니 백준 채점 도중 런타임 에러가 발생했다.

만일 while문을 돌다가 start = 0, end = 1이 되는 경우 mid = 0이 된다.

아래 코드처럼 lan을 mid로 나눠주어 만들 수 있는 랜선의 갯수(cnt)를 계산해야 하는데, mid = 0이 된다면 ZeroDivisonError가 발생한다.

따라서 start = 1로 설정해주었다.

for lan in lans:
    cnt += (lan // mid ) # ZeroDivisionError

---

참고문헌

https://www.acmicpc.net/board/view/110825