[백준] 1654 랜선 자르기 (파이썬 python)

 

 

문제 링크

 

 

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

1654번: 랜선 자르기

 

 

문제

 

 

 

 

 

문제 풀이

 

 

이분 탐색으로 풀이를 하면 되는 문제이다.

길이를 기준으로 랜선의 개수를 결과내면 된다.

1을 시작값, 입력받은 길이 중 최댓값을 마지막값으로 하여 중간값을 정하고

해당 중간값으로 길이를 나누어 나온 개수를 합쳐

해당 개수가 요구받은 N값보다 작을 경우 중간값을 줄이기 위해 end 값을 mid - 1로,

N값보다 클 경우 중간값을 늘리기 위해 start 값을 mid + 1로 변경한다.

 

import sys

K, N = map(int, input().split())
len = [int(sys.stdin.readline()) for _ in range(K)]
start, end = 1, max(len)  # 이분탐색 처음과 끝위치

while start <= end:  # 적절한 랜선의 길이를 찾는 알고리즘
    mid = (start + end) // 2  # 중간 위치
    lines = 0  # 랜선 수
    for i in len:
        lines += i // mid  # 분할 된 랜선 수

    if lines >= N:  # 랜선의 개수가 분기점
        start = mid + 1
    else:
        end = mid - 1
print(end)