[이분탐색] 백준 #1654 랜선 자르기 - Python

🗂️ 문제

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

 

💡 접근법

“N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다.”라는 문제 조건에 따라 이분탐색의 기준을 필요한 랜선 개수 이상인지 이하인지 따라 범위를 좁혀나간다. 따라서 만들 수 있는 랜선의 수가 N개일 때 종료조건을 걸지 않고 계속해서 범위를 좁혀나가면서 최대의 랜선 길이를 구한다.

 

더이상 탐색 범위가 좁혀지지 않을때 high 값이 가장 긴 랜선의 길이가 되어 출력된다.

 

😎 내 코드

import sys

K, N = map(int, sys.stdin.readline().split())
line = [int(sys.stdin.readline()) for _ in range(K)]

def cal_line_num(height):
    sum = 0
    for l in line:
        sum += l // height
    return sum

low = 1
high = max(line)

while (low <= high):
    mid = (low+high) // 2 # 랜선의 길이
    mid_line_num = cal_line_num(mid) # 랜선의 개수
    print(mid, mid_line_num, low, high)
    
    if mid_line_num >= N:
        low = mid + 1
    else:
        high = mid - 1

print(high)

 

✅ 정답 확인