[Python]백준 BaekJoon.AC 1654 : 랜선 자르기(이진탐색, 런타임 에러)

 

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

1654번: 랜선 자르기

 

 

 

예기치 않은 곳에서 오류를 만난 문제다.

 

여느때처럼 K와 N을 받고, 랜선 길이들을 리스트에 넣고.

그 리스트를 정렬해 가장 긴 랜선 길이를 뽑아 최댓값으로 정해줬다.

 

이제부턴 그냥 이진탐색 구현!

중간값(mid) 지정 후 랜선 리스트를 돌며 자를 수 있는 랜선 길이들을 모두 카운팅 해줬다.

만약 이 개수가 N보다 크거나 같으면 우선 result에 저장.

구할 수 있는 최대 길이까지 구한 후 result를 출력하면 된다. 

 

 

정답비율이 너무 낮길래, 혹시 놓친 부분은 없는지 제출하기 직전까지 여러번 확인해줬다.

그런데 채점결과는 런타임 에러 (ZeroDivisionError)

0을 나눴다는 거다.

 

 

<틀린코드>

K, N = map(int, input().split())
lan = []

for n in range(N):
    lan.append(int(input()))

lan.sort()
sta = 0
fin = lan[-1]
mid = -1
result = 0

while sta <= fin:
    count = 0
    mid = (sta + fin) // 2
    for l in lan:
        count = count + l // mid

    if count >= N:
        sta = mid + 1
        result = mid
    elif count < N:
        fin = mid - 1

print(result)

 

 

 

다시 코드를 살펴보니, 중간값(mid)이 원인이었더라.

 

예시)

1 1

1

 

 

이를 어떻게 해결할까 고민하다 처음엔 mid가 0이면 break를 걸어줬다.

그러니 이젠 아예 틀렸다고 채점해줬다...

 

 

결론부터 말하자면 최솟값(sta)을 1로 설정해줘야 했다.

 

 

mid = (sta + fin) // 2

위 식을 지정할 때 mid는 0이 아니어야 하니까,

sta와 fin을 재설정해줘야 했다.

fin은 입력받은 랜선들 중 가장 긴 랜선이며, 랜선 길이의 조건은 1이상이니 괜찮다.

(0+1)//2 = 0

이 경우를 피해야 했고, sta를 1로 지정해주는 간단한 수정으로 문제를 통과했다.

 

 

덕분에 삽질 쬐끔 했다..

경우에 따라 다를 수 있겠지만 0이 해당되지 않는 조건의 문제를 푼다면 앞으론 최솟값을 1로 지정해줘야겠다.

그리고 0을 나누는 실수를 놓쳐선 안되겠다.

 

 

 

K, N = map(int, input().split())
lan = []

for n in range(K):
    lan.append(int(input()))

lan.sort()
sta = 1
fin = lan[-1]
mid = -1
result = 0

while sta <= fin:
    count = 0
    mid = (sta + fin) // 2
    for l in lan:
        count = count + l // mid

    if count >= N:
        sta = mid + 1
        result = mid
    elif count < N:
        fin = mid - 1

print(result)