[파이썬, Python] 백준 1654: 랜선 자르기

문제

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

1654번: 랜선 자르기

코드

import sys
input = sys.stdin.readline

k, n = map(int, input().split())
lan = [int(input()) for _ in range(k)]
start, end = 1, max(lan)

while start <= end:
    mid = (start+end) // 2
    lines = 0
    for i in lan:
        lines += i // mid
        
    if lines >= n:
        start = mid + 1
    else:
        end = mid - 1
print(end)

설명

우선 랜선의 길이를 각각 입력한 리스트를 만들어준다.

이후 시작은 1로 end는 랜선의 길이중 가장 긴 랜선으로 설정해 준다.

만약 start가 end보다 작다면 계속 루프를 하는데,
이때, mid 지점을 start와 end의 중간 지점으로 설정해 준다.

모든 랜선을 mid 값으로 나눈 몫을 lines에 더해주고,
만약 lines가 필요한 개수인 n보다 많다면 길이를 더 늘릴 수 있으므로
start를 mid보다 1 큰 수로 설정하여 다시 루프를 돌려주고,
그렇지 않다면 길이를 줄여야 하므로 end를 mid보다 1 줄여서 값을 조정해 준다.

모두 반복하여 start값이 end 값보다 커지게 되면 이때의 end가 최대 길이므로 end를 출력한다.