[BOJ][python] 1654. 랜선 자르기

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

1654번: 랜선 자르기

---

💡IDEA

이분 탐색을 사용하는 문제이다.

2022.07.31 - [Algorithm/BOJ] - [BOJ][python] 2110. 공유기 설치 문제를 풀었던 것이 도움이 되었다.

랜선 길이를 찾기 위해서 왼쪽 값(l)은 1, 오른쪽 값(r)은 랜선 길이의 최댓값으로 초기화해주었다.

N개 이상의 랜선을 가져야 하는데, 랜선의 개수는 모든 랜선을 이분탐색하며 중간 값(m)으로 나눈 몫의 합이다. 이렇게 구한 개수가 N개 이상인 경우에 랜선의 최대 길이를 m으로 갱신한다. 이 때 랜선의 개수가 N과 크거나 같더라도 그 때의 길이가 반드시 최대길이는 아님에 주의해야 한다.

랜선의 개수가 N개 이상인 조건에 만족하는 선에서 랜선의 길이를 최대한 늘리며(l=m+1) 계속 이분탐색을 진행한다. 조건을 만족하지 못한다면 랜선의 길이를 줄여서(r=m-1) 조건에 맞도록 진행한다.

 

📌CODE

import sys
input = sys.stdin.readline

K, N = map(int, input().split())
lengths = sorted([int(input().strip()) for _ in range(K)])

ans = 0
l = 1
r = lengths[K-1]
while l<=r:
    m = (l+r)//2
    cnt = 0
    for i in range(K):
        cnt += lengths[i] // m
    if cnt >= N:
        ans = max(ans, m)
        l = m+1
    else:
        r = m-1

print(ans)