[코테]99클럽 코테 스터디 2일차 TIL 백준 1654 랜선자르기

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

백준에서 이분탐색의 두번째 문제로 랜선자르기 문제를 풀어보았다. 

이전에 암기왕에서 이분탐색 알고리즘을 그대로 사용했다면, 이번 문제는 실버2 단계의 문제인 만큼 조금의 응용이 필요했다. 기본 이분탐색 알고리즘이 정렬된 리스트에서 찾고자 하는 숫자의 인덱스 정보를 이분법으로 나누어 찾았다면, 이번 문제는 start, end의 값을 랜선의 길이로 바꾸어주어야 했다...! 

 

import sys

read = sys.stdin.readline

K, N = map(int, read().split())

lans = []

for _ in range(K):

    lans.append(int(read()))

def binary_search(data):

    start = 1

    end = max(data)

    while start <= end:

        mid = (start + end) // 2

        target = 0

        for d in data:

            target += (d // mid)

        if N > target:

            end = mid - 1

        else:

            start = mid + 1

    return end

print(binary_search(lans))