[백준][binary search] 랜선 자르기 python (200928)

 

 

1. 문제 설명 

 

www.acmicpc.net/problem/1654

1654번: 랜선 자르기

 

2. 풀이 

 

우선 N개로 분할되는 최대 랜선 길이를 탐색해야한다  --> binary search @ 

이때 최대로 되는 값을 찾기 때문에 일반적으로 알고 있는 이진 탐색 코드와는 조금 다르다. 

 

## 1654- 랜선 길이 자르기
num_list_len, key = map(int,input().split())
global num_list
num_list = []
for i in range(num_list_len):
    num_list.append(int(input()))

### 랜선의 갯수를 맞추되 길이는 최대로 할 수 있는 길이를 탐색
start = 1
end = max(num_list)
while start <= end:
    mid = (start + end) // 2
    # print(f" start:{start},end:{end}, mid:{mid}")
    output = sum([lan // mid for lan in num_list])

    if output < key:  ## 갯수가 기준보다 작게나옴 --> 랜선 길이를 더 줄여야함
        end = mid - 1  # 랜선 길이 탐색범위를 작게 잡음
        print("output<<<<key --> 랜선길이 더 줄여")
    else:  ## 갯수가 딱 맞거나 더 많이 나옴 --> 랜선 길이를 더 늘려봅세~
        start = mid + 1
        print("output>=key --> 랜선길이 더 늘여")
print(f"FINAL ==> start:{start},end:{end}, mid:{mid}")
print(end)

 

즉 랜선 개수가 딱 맞더라도, 랜선 길이를 더 늘리는 식으로 하여 최대값을 산출하는 것 ! 

그렇게 늘리다가 startnum 이 endnum을 넘게 되는 순간 탐색이 멈추게 된다. 

 

가령 

5 3
10
10
10
10
10

이렇게 입력 할 경우 

Midnum : 5  // output>=key --> 랜선길이 더 늘여
Midnum : 8  // output>=key --> 랜선길이 더 늘여
Midnum : 9  // output>=key --> 랜선길이 더 늘여
Midnum : 10 // output>=key --> 랜선길이 더 늘여
FINAL ==> start:11,end:10, mid:10

이런 식으로 이미 5로 조건을 만족하더라도 계속 수를 늘려나가면서 max 값을 구한다. 

 

 

3. 정리 

반대로 최소 값을 갖는 문제도 살펴보자 !! 

 

mr-dan.tistory.com/14

도로에 가로등 전구 달기