백준 1654 - 랜선 자르기 (Python3)

코드

k, n = map(int, input().split())

lan = []

for _ in range(k):
    lan.append(int(input()))
    
# 최소 길이 1
# 최장 길이 => 가지고 있는 랜선 중 최장 길이
# start = 1 end = max(lan)
start = 1
end = max(lan)  

# 최대 랜선 길이
target = 0

# 이진 탐색 구현
def binary_search(arr, target, start, end):
    while start <= end:
        
        # 만들 수 있는 랜선의 개수
        line = 0
        
        # 이진탐색을 할 것이므로 mid를 설정
        # 단 이때, mid의 길이가 사실상
        # 우리가 찾고자 하는 target의 값이라고 생각하면 됨
        mid = (start + end) // 2
        
        # 가지고 있는 랜선들을 mid로 나누어서
        # n과 같아지는 지 확인
        # 어차피 1 ~ 최장 길이 까지 확인할 것이므로
        # 굳이 정렬할 필요없음
        for l in lan:
            line += l // mid
            
        # 원하는 랜선의 개수 n보다 크거나 같은 경우
        # 최단 길이를 1씩 증가 시킴
        if line >= n:
            target = mid
            start = mid + 1
        else:
            end = mid - 1
            
    return target

binary_search(lan, target, start, end)

문제 해설

전형적인 이진탐색 문제이다.

(2022-04-16) 2달만에 다시 풀어봤는데 감을 잃어서 다시 한 번 정리하였다 ㅠㅠ

이진 탐색