[BOJ] 랜선자르기

---

코드

from sys import stdin
input = stdin.readline

k, n = list(map(int, input().split(' ')))
lan = [int(input()) for _ in range(k)]

start, end = 1, max(lan)

while start <= end:
    mid = (start + end) // 2
    pieceNum = sum([l // mid for l in lan])
    if pieceNum < n:
        end = mid - 1
    elif pieceNum >= n:
        start = mid + 1
print(end)

결과

풀이 방법

• 만들 수 있는 최대 랜선의 길이를 찾아야 하는데 랜선의 길이가 최대 2^31-1이기 때문에 브루트포스를 활용할 수는 없고 이분탐색을 활용하였다
• start = 1, end = 입력받은 랜선 중 가장 긴 랜선 길이 로 설정해 놓고 중간값(mid)으로 랜선을 나누어서 나누어진 조각 개수를 확인해 본다
• 조각개수가 필요한 개수 n보다 작으면 mid를 더 작게 해야하므로 end = mid - 1 으로 재설정한다
• 조각개수가 필요한 개수 n보다 많으면 더 큰 mid를 찾아보기 위해 start = mid + 1 으로 재설정한다
• start == end가 되는 지점이 구하는 최대 랜선의 길이가 된다

---