Python - [백준]1654-랜선 자르기

출처

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

문제

가지고 있는 랜선들을 잘라 균일한 크기로 최소 K개의 랜선을 만들어야 할 때, 자를 수 있는 최대 길이를 구하는 문제이다.

접근 방법

모든 경우에 대해 탐색을 진행 할 수는 없다. 이런 경우는 이분탐색을 사용하여 접근하는 것이 효율적이다.
길이의 범위는 1부터 가장 긴 랜선의 길이가 될 것이다. 이 중간점의 길이를 보고 랜선의 최소 최대를 업데이트 하면 된다.

풀이

• start와 end를 설정하여, 그 중간 값인 mid길이로 잘랐을때 K개 보다 작다면, mid 위로는 볼 필요가 없다. End를 mid-1로 두고 다시 탐색을 진행한다.

• mid로 자른게 K보다 많다면, mid 밑으로는 볼 필요가 없다. start를 mid+1로 두고 다시 탐색을 진행한다.

• 그렇게 구한 최대 값을 저장해두었다가 while문이 끝나면 출력한다.

코드

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
arr = [int(input()) for _ in range(n)]
start, flag = 1, max(arr)
max_len = 0
while start <= flag:
    now_len = (start + flag) // 2
    tmp = 0
    for i in arr:
        tmp += i//now_len
    if tmp < k:
        flag = now_len - 1
    else:
        start = now_len + 1
        max_len = now_len
        
print(max_len)