boj1624 - 랜선자르기

문제: 랜선자르기
parametric search - 최적화 문제를 결정문제(예, 아니오)로 바꾸어 해결함 --> 이진탐색 사용

end = 가지고 있는 랜선 길이의 합 // 필요한 랜선 개수 -> 초기 길이
total = 각 랜선 길이를 mid로 나누어 더함 (=그 길이(mid)를 갖도록 잘랐을 때 나올수 있는 랜선의 갯수)

if ) total이 갯수보다 크거나 같으면 (조건 만족) -> mid 저장해놓고
start 더 크게 해서 mid 길이 최적화

else ) total이 갯수보다 작으면 (조건 불만족) -> end 작게 해서 다시 이진 탐색

• if (start+end) >= 2:
  test case가
  4 13
  10
  1
  1
  1
  일때 ,
  mid 가 0이 되어 devidebyzero -> runtime error
  따라서 start + end 가 2보다 작으면 그 합을 mid로 설정

import sys

if __name__ == '__main__':
    input = sys.stdin.readline

    K, N = map(int, input().split())
    lan = []
    for _ in range(K):
        lan.append(int(input()))
    lan.sort()

    start = 0
    end = sum(lan) // N
    result = 0

    while start <= end:
        total = 0
        if (start+end) >= 2:
            mid = (start+end) // 2
        else:
            mid = start+end
        # print('mid :', mid)
        for i in lan:
            total += i // mid
        if total >= N:
            result = mid
            start = mid + 1
        else:
            end = mid -1

    print(result)