[BOJ] 백준 1654 랜선 자르기 / 이분탐색

이미지를 클릭하면 문제 사이트로 이동합니다.

 

 

💭 문제 이해

영식이가 가지고 있는 K개의 랜선을 N개 이상의 동일한 길이의 선들로 만들기 위해

자를 길이를 찾아야하는 문제이다.

 

랜선의 길이는 최대 2³¹-1로 완전탐색을 하게 되면 시간초과가 발생하게 된다.

이분탐색을 통해서 무리 없이 해결할 수 있는 문제이다.

 

 

 

구현 언어: Python

 

 

import sys
from collections import Counter

r = sys.stdin.readline


def binary_search(target_cnt: int, lines: list) -> int:
    result = 0
    left = 1
    right = max(lines)

    while left <= right:
        mid = (left + right) // 2
        # mid 길이 기준으로 만들어진 랜선의 수
        made = sum(line // mid for line in lines)
        if target_cnt <= made:
            result = mid
            left = mid + 1
        else:
            right = mid - 1
    return result


k, n = map(int, r().split())
lines = [int(r()) for _ in range(k)]
print(binary_search(n, lines))