[백준/BOJ] - 1654번 python 풀이 - 이분탐색(binary search)

---

Key Point 

1. 자르기 문제는 보통 이분탐색을 활용하면 쉽게 해결 가능하다.

 

2. 보통 이분탐색의 세팅을 while start<= end:로 놓는데 이렇게 하면 예외 처리가 되지 않아 오류가 발생한다.

주어진 랜선의 최댓값이 1인 경우, start = 0, end = 1로 시작하기 때문에 mid = (start + end) // 2에서 몫이 0이 되므로

mid를 나누는 수로 사용하는 해당 코드에서는 문제가 생길 수 밖에 없다.

그렇기에 start =0, end = 1일 때 mid 값을 1로 설정해준다.

 

3. start와 end가 모두 0일 경우에도 while문의 조건에 해당되며 mid 값이 0이 나오기에 mid를 나누는 수로 사용하는 부분에서 오류가 생긴다. 그렇기에 해당 경우에는 의미가 없는 탐색이므로 break 하여 반복문을 탈출한다.

 

※

4. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다.

라는 문구가 있기 때문에

자른 랜선의 개수가 N값과 일치하지 않고 이보다 큰 경우에도 조건에 해당되니 참고하자.

 

알게 된 점

-  이분탐색을 진행하는데 예외처리가 분명 발생할 수 있기 때문에 문제의 조건을 정확히 파악하자.

---

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

start = 0
end = max(lan)
res = 0

while start <= end:
    if start == 0 and end == 1: #주어진 랜선의 최댓값이 1인 경우
        mid = 1
    elif start == 0 and end == 0: #mid가 0이되면 나누는 부분에서 오류생김
        break
    else:
        mid = (start + end)//2

    total = 0

    for i in lan:
        total += i // mid
    if total >= M:
        res = mid
        start = mid + 1
    else:
        end = mid - 1
print(res)