[백준] 1654. 랜선 자르기 - Python

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

1654번: 랜선 자르기

---

• 생각
  • 길이를 이분 탐색으로 찾기
    • 처음에는 길이 합을 필요한 랜선의 개수로 나눈 그 숫자부터 찾으려고 했으나 시간초과를 우려해 이분탐색으로 바꿨다. 이전에 '나무 자르기' 문제를 푼 것이 많이 도움이 되었다.
• 코드

input = stdin.readline

# 이미 가지고 있는 랜선의 개수, 필요한 랜선의 개수
K,N = map(int,input().split())

# 가지고 있는 랜선 길이
lines = []
for _ in range(K):
    l = int(input())
    lines.append(l)

# 이분 탐색
start = 1
end = max(lines) 

while start <= end:
    cnt = 0
    mid = (start + end) // 2
    # 랜선 자르기
    for line in lines:
        cnt += line // mid
    # 잘린 랜선이 원하는 갯수보다 많다면 길이를 늘리기
    if cnt >= N:
        start = mid + 1
    else:
        end = mid - 1

print(end)