[백준 1654 파이썬] 랜선 자르기 (실버2, 이분탐색)

알고리즘 유형 : 이분 탐색
풀이 없이 스스로 풀었나요? : ⭕

---

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

솔루션

1. 이분 탐색 범위를 1 ~ 랜선 중 가장 긴 길이로 제한

2. 이분 탐색 시작

3. 모든 랜선 값을 mid로 나누어 총 몇개의 랜선이 나오나 살펴본다.

4. 랜선이 목표치 이상이면 res에 mid 저장 후 mid + 1을 lt로 두고 다시 while문 반복

5. 랜선이 목표치 이하면 mid - 1을 rt로 두고 다시 while문 반복

6. 이분탐색 종료되면 결과 값인 res 출력

소스 코드

import sys

input = sys.stdin.readline

def count(num):
    cnt = 0
    for line in lines:
        cnt += line // num
    return cnt

if __name__ == "__main__":
    k, n = map(int, input().split())
    lines = [int(input()) for _ in range(k)]
    lt, rt = 1, max(lines)
    res = 0

    while lt <= rt:
        mid = (lt + rt) // 2
        if count(mid) >= n:
            res = mid
            lt = mid + 1
        else:
            rt = mid - 1

    print(res)