[Python] boj no. 1654 : 랜선 자르기

Problem

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

Idea

이분 탐색으로 해결. 각 랜선을 left와 right의 중간값인 mid 값으로 나눈 몫을 더하면 mid 길이로 랜선을 만들었을 때의 랜선 갯수의 합을 알 수 있다.

1. 랜선 갯수가 K보다 크거나 같은 경우, 랜선의 길이를 늘려볼 수 있을 것으로 간주하고 탐색의 경계를 mid~right 로 설정하여 다시 탐색한다.
2. 랜선 갯수가 K보다 작은 경우, 랜선의 길이를 줄여야하므로 탐색의 경계를 left~mid로 설정하여 다시 탐색한다.
3. left == right 인 경우, 해당 값이 K개의 랜선을 만들 수 있는 최대 길이이다.

Code

import sys

input = sys.stdin.readline

K, N = map(int, input().split())
lane = [int(input()) for _ in range(K)]

left = 1
right = max(lane)

while left <= right:
    mid = (left + right) // 2
    num = 0
    
    for l in lane:
        num += (l // mid)
    
    if num >= N:
        left = mid + 1
    elif num < N:
        right = mid - 1
    
print(right)

Comment