(Python) - BOJ(1654번) : 랜선 자르기

 

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

1654번: 랜선 자르기

---

• 해설 : 

K개의 랜선 길이가 주어지고, 이 K개의 랜선을 동일한 길이로 잘라 N개의 랜선을 만들려 한다.

이 때 자를 수 있는 랜선의 최대 길이를 찾는 문제이다.

 

 

 

---

• 풀이 :

이분탐색으로 쉽게 해결할 수 있는 문제이다. start는 0, end는 랜선의 길이들 중 최댓값으로 설정하고 

각 탐색마다 자른 랜선의 개수가 K개보다 작으면 길이를 줄이고, 크거나 같다면 길이를 늘려 최종적으로 최댓값을 찾으면 된다.

 

 

 

---

• 소스코드 : 

 

import sys
input = sys.stdin.readline
 
k,n = map(int,input().split())
l = [int(input().strip()) for _ in range(k)]
i = 1
j = max(l)
while i <= j:
    mid = (i+j)//2
    cnt = sum([key // mid for key in l])
    if cnt >= n:
        i = mid + 1
        ans = mid
    elif cnt < n:
        j = mid - 1
print(ans)