백준 1654번(랜선 자르기) 파이썬

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

1654번: 랜선 자르기

전형적인 이분탐색 문제였다.

전날에 살짝 봤지만 컨디션 난조로 오래걸릴거 같아 냅두고 다음날 풀었는데 금방 풀렸다.(너무 졸렸음ㅋㅋ;;)

아래는 풀이 코드이다.

import sys
input = sys.stdin.readline

k,n = map(int,input().split())
line = [] # 전선을 입력 받을 리스트
ans = [] # 11개가 맞아 떨어지는 정답들을 넣을 리스트
for i in range(k):
    line.append(int(input())) 


def BS(array,t,start,end):
    total = 0 # n과 비교할 total변수다
    if start>end:
        return None
    mid = (start+end)//2
    for i in array:
        total += i//mid # 각각의 전선들과 나눠주면서 몫을 더해준다
        
    if total >= t: # 그렇게 더한 몫이 t와 같거나 크면  
        ans.append(mid) # 정답 리스트에 넣어준다
        return BS(array,n,mid+1,end) # 그리고 다시 재귀를 돌려준다 
    else:
        return BS(array,n,start,mid-1) # total이 t보다 작을 경우 범위를 수정해 재귀를 돌려준다
    
BS(line,n,1,max(line)) # start가 0이 아닌 1부터 시작하는 이유는 선이 0m일 수는 없기 때문이다

print(max(ans)) # 최댓값을 출력해준다.

처음에 문제를 제출했을때 81%에서 zerodivisionerror가 떴었다. 이건 0으로 나눌경우에 나오는 에러인데 이게 자꾸 왜 생기는지 확인했다. 문점은 처음에 BS(line,n,0,max(line))이라고 실행을 시켰다. mid를 구할때 1+0이 실행되어 1//2라는 수식이 실행되 mid가 0이 되어버리는 문제점이였다. 즉 내가 선은 0m가 있을 수 없다는것을 잊고 start를 0으로 두고 실행한 것이였다. 그래서 1로 바꿨더니 아주 잘 실행됐다 ^^