[백준] 1654번 랜선 자르기 (feat.Binary Search)이분 탐색

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

1654번: 랜선 자르기

문제 풀이를 하면서 햇갈렸던 부분에 대해서 정리하고 넘어가고자 글을 작성한다.

풀이를 완료한 코드는 아래와 같다.

import sys

k, n = map(int, input().split())
k_list = []
for i in range(k):
    k_list.append(int(sys.stdin.readline().rstrip()))


# -------------------- binary search 사용 코드 -----------------------
k_list.sort()   # 가장 길이가 긴 케이블을 구하기 위해 정렬
best_long = k_list[-1]  # 가장 길이가 긴 케이블을 best_long에 저장
start = 1
end = best_long

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

    for i in k_list:
        cable_count = cable_count + (i // mid)

    if cable_count >= n:
        start = mid + 1
    else:
        end = mid - 1
print(end)

최종 반환값은 end여야 하는데, 첫번째로 풀이할 때는, 당연히 mid값을 반환해야 한다고 생각했다.

이번 문제를 위코드로 풀이할 때, end가 최종 반환값이어야 하는 이유에 대해서 정리해보자.

문제에 제시되어 있는 예제를 위의 코드에 대입해보자.

k = 4, n = 11
k_list = 802, 743, 457, 539
start = 1
end = 802
로 시작한다.

while문을 수행하는데, start<=end 가 참일때 계속 반복된다.

[1회전]
cable_count = 0
mid = (1 + 802)//2 = 401
cable_count = 0 + (802//401) = 2
cable_count = 2 + (743//401) = 3
cable_count = 3 + (457//401) = 4
cable_count = 4 + (539//401) = 5

cable_count가 n인 11보다 작은 5이므로 
end = 401 - 1 = 400

[2회전]
cable_count = 0
mid = (1 + 400) // 2 = 200
cable_count = 0 + (802//200) = 4
cable_count = 4 + (743//200) = 7
cable_count = 7 + (457//200) = 9
cable_count = 9 + (539//200) = 11

cable_count가 n인 11과 같은 11이므로 이때의 mid를 반환하면 정답이라고 생각했었다.
그래서 원래는 while 로직안에 
if cable_count == n:
  print(mid)
   break
라는 로직을 넣었고, 정답 제출을 그대로 제출 했었으나 오답처리 되었다.

원래 제출 했던데로 문제풀이 로직을 구현하면 안되는 이유는 다음과 같다.
테스트 케이스에 따라서 cable_count가 n과 일치하는 경우가 없을 수 있다.
문제에서 중요한 조건이 있었는데  
"N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. " 라는 조건이 중요하다.
즉, N개를 만드는 조각의 길이를 반환하는 것이 아니라,
조각의 길이를 줄이며 처음으로 N개 이상이 만들어지는 길이를 구하는 것이 핵심이다.

물론 특정 mid일때, n == cable_count인 경우도 있을 수 있다. 하지만 테스트 케이스에 따라 없을 수도 있다.
따라서, cable_count == n 일때 mid를 반환하도록 로직을 구성하면 안되고,
while(start<=end): 이렇게 구성한 while문을 끝까지 반복되도록 하여 끝까지 탐색을 진행해야 한다.

위에서 진행하던 while문 회전을 계속 진행해보자.

2회전에서 for문을 로직에서 빠져나온 후 cable_count = 11이므로
if-else문에서
if cable_count >= n: 문이 참이되어
start = mid + 1을 수행하게 된다.
start = 200 + 1 = 201 이 된다.

[3회전]
cable_count = 0
mid = (201+400)//2 = 300
cable_count = 0 + (802//300) = 2
cable_count = 2 + (743//300) = 4
cable_count = 4 + (457//300) = 5
cable_count = 5 + (539//300) = 6

cable_count가 n인 11보다 작은 6이므로
end = 299

[4회전]
cable_count = 0
mid = (201+299)//2 = 250
cable_count = 0 + (802//250) = 3
cable_count = 3 + (743//250) = 5
cable_count = 5 + (457//250) = 6
cable_count = 6 + (539//250) = 8

cable_count가 n인 11보다 작은 8이므로 
end = 249

[5회전]
cable_count = 0
mid = (201+249)//2 = 225
cable_count = 0 + (802//225) = 3
cable_count = 3 + (743//225) = 6
cable_count = 6 + (457//225) = 8
cable_count = 8 + (539//225) = 10

cable_count가 n인 11보다 작은 10이므로
end = 224

[6회전]
cable_count = 0
mid = (201+224)//2 = 212
cable_count = 0 + (802//212) = 3
cable_count = 3 + (743//212) = 6
cable_count = 6 + (457//212) = 8
cable_count = 8 + (539//212) = 10

cable_count가 n인 11보다 작은 10이므로
end = 211

[7회전]
cable_count = 0
mid = (201+211)//2 = 206
cable_count = 0 + (802//206) = 3
cable_count = 3 + (743//206) = 6
cable_count = 6 + (457//206) = 8
cable_count = 8 + (539//206) = 10

cable_count가 n인 11보다 작은 10이므로
end = 205

[8회전]
cable_count = 0
mid = (201+205)//2 = 203
cable_count = 0 + (802//203) = 3
cable_count = 3 + (743//203) = 6
cable_count = 6 + (457//203) = 8
cable_count = 8 + (539//203) = 10

cable_count가 n인 11보다 작은 10이므로
end = 202

[9회전]
cable_count = 0
mid = (201+202)//2 = 201
cable_count = 0 + (802//201) = 3
cable_count = 3 + (743//201) = 6
cable_count = 6 + (457//201) = 8
cable_count = 8 + (539//201) = 10

cable_count가 n인 11보다 작은 10이므로
end = 200

 

그런데 이때, while(start <= end):가
start = 201, end = 200이므로 false가 되어 while문이 종료된다.

그리고, 현재 상태의 end를 반환한다.
왜냐하면 200을 분기점으로 길이가 더 길어지면, cable_count가 n보다 작아지기 때문이다.
그리고 200을 분기점으로 길이가 더 작아지면 cable_count 갯수가 n보다 항상 많다.

그런데 이 문제는 "n개의 랜선을 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성" 하는 것이므로,
while(start <= end):를 할 때,
cable_count == n인 경우 탐색을 멈추지말고,
start<=end가 false가 될 때 까지 탐색을 하여
while문을 false로 만든 mid값에서 -1을한 값
즉 end = mid - 1이므로 
즉 임계값에 있는 end를 반환하는 것이 적절하다.

앞서 말했듯,
N개를 만드는 조각의 길이를 반환하는 것이 아니라,
조각의 길이를 줄이며 처음으로 N개 이상이 만들어지는 길이를 구하는 것이 핵심이다.

즉, 임계값에 도달할때 까지 길이를 줄여왔으므로 mid-1인 end를 반환해야 한다.