177. 1654(랜선 자르기) - 파이썬

import sys
input = sys.stdin.readline

K, N = map(int, input().split())
lanLine = list(int(input()) for _ in range(K))

start = 1
end = max(lanLine)

while(end - start >= 0):
    mid = (start + end) // 2
    lines = 0

    for val in lanLine:
        lines += val // mid

    if lines >= N:
        start = mid + 1
    else:
        end = mid - 1

print(end)

문제요약

주어진 랜선들로 원하는 개수만큼의 랜선을 최대한 크게 잘라보아라.

설명

문제를 처음보면 무슨소리인가 라는 생각이 들 것 이다.

문제를 풀어서 설명해보면

K개의 랜선을 가지고 있는데 N개로 만들려고한다.

K개의 랜선을 같은 길이로 잘라 N개를 만드는데 자를때 가장 긴 길이로 만들라는 뜻이다.

 

백준에 있는 예제를 가지고 이분탐색을 이용하여 문제를 풀어보겠다.

802 / 743 / 457 / 539 길이의 랜선이 있고 이를 자를 수 있는 경우의 수는 1cm ~ 802cm 이다.

여기에 이분탐색을 이용해보자.

start는 1 end는 802로 설정하고 이 둘을 더해 2 나눈 403이 mid값으로 설정된다.

start = 1
end = max(lanLine)

while(end - start >= 0):
    mid = (start + end) // 2
    lines = 0

    for val in lanLine:
        lines += val // mid

을 통해 나온 랜선의 개수 총합이 만약 N보다 크거나 같다면 mid를 중심으로 오른쪽이라는 이야기로 start 값을 mid +1로 바꿔주면 된다.

 

반대로 N보다 작다면 mid를 중심으로 왼쪽이라는 이야기로 end값을 mid -1로 해주면 된다.

 

이런식으로 이어가다보면 start가 end보다 커지는 상황이 발생한다.(mid로 나눈 랜선의 개수가 N보다 크거나 같을 때, start만 조절하기 때문이다.)

    if lines >= N:
        start = mid + 1
    else:
        end = mid - 1

 

그 때 end가 N개의 선을 만족시키고, 자를 수 있는 가장 큰 랜선의 길이이다.

print(end)