[백준] 1654번 - 랜선 자르기

아이디어

나무 자르기 문제와 너무 유사했다.
단지, 체크해야 하는 부분이 다르다는 점? 나무 자르기는 자른 나무를 합한 값을 체크해야 했고, 랜선 자르기는 랜선의 수를 체크해야 했다.
따라서, 나무 자르기에서는 check값에 (나무 - mid)값을 넣어주었다면, 랜선 자르기에서는(랜선 // mid)값을 넣고 비교하였다.

1차 시도

# 랜선 자르기
import sys

K, N = list(map(int,sys.stdin.readline().rstrip().split()))
lan = [int(sys.stdin.readline().rstrip()) for x in range(K)]

start = 0
end = max(lan)

result = 0
while(start <= end):
    check = 0
    mid = (start + end) // 2
    for l in lan:
        check += (l // mid)
    if check < N:
        end = mid -1
    else:
        result = mid
        start = mid + 1

print(result)

런타임 에러 발생 (ZeroDivisionError)
-> 아마, l // mid 과정에서 에러가 발생한게 아닐까 생각된다.

2차 시도

# 랜선 자르기
import sys

K, N = list(map(int,sys.stdin.readline().rstrip().split()))
lan = [int(sys.stdin.readline().rstrip()) for x in range(K)]

start = 0
end = max(lan)

result = 0
while(start <= end):
    check = 0
    mid = (start + end) // 2
    for l in lan:
        try:
            check += (l // mid)
        except ZeroDivisionError:
            pass

    if check < N:
        end = mid -1
    else:
        result = mid
        start = mid + 1

print(result)

try, except로 에러만 처리해줬는데, 역시 그냥 패스하니까 계산을 제대로 하지 못하게 되었고 결과적으로 '틀렸습니다'가 떴다.
반례)
5 5
1
1
1
1
1
답 : 1
내 답변 : check += (l // mid) ZeroDivisionError: integer division or modulo by zero
=> 역시나 이 부분에서 0으로 나눠주는 부분으로 인해 에러가 발생한 것이 맞았다.

3차 시도

# 랜선 자르기
import sys

K, N = list(map(int,sys.stdin.readline().rstrip().split()))
lan = [int(sys.stdin.readline().rstrip()) for x in range(K)]

start = 1
end = max(lan)

result = 0
while(start <= end):
    check = 0
    mid = (start + end) // 2
    for l in lan:
        check += (l // mid)
    if check < N:
        end = mid -1
    else:
        result = mid
        start = mid + 1
print(result)

start값을 0으로 지정해둘 경우 end 값이 1이면 mid값이 0이 되면서 ZeroDivisionError가 발생한다.
문제의 조건에서 모든 값들이 자연수, 1이상의 정수값이므로 start값을 1로 변경해주었다.