Algorithm (PS)

[백준] 1654번 랜선자르기 Python - 이진탐색

minjiwoo 2022. 12. 31. 13:20
728x90

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

 

1654번: 랜선 자르기

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그

www.acmicpc.net

k, n = map(int, input().split())
lines = []
for i in range(k):
    lines.append(int(input()))

start = 1
end = max(lines)
while start <= end:
    count = 0
    mid = (start+end)//2
    for i in lines:
        count += i//mid
    if count < n: # 자르는 길이를 줄여야 한다
        end = mid-1
    else: # 같거나 더 많음 -> 랜선 길이를 늘려도 된다
        start = mid+1

print(end)
728x90