1654 랜선 자르기

💡문제 분석 요약

• 이미 가지고 있는 랜선들은 길이가 제각각이다. 이것들을 이용해서 n개의 랜선이 더 필요하다.
• 갖고 있는 랜선들을 n개로 만들 때, 최대길이가 되어야한다.

💡알고리즘 설계

• 지난번 풀었던 절단기 문제와 매우 유사해서 쉽게 풀 수 있었다. 이분탐색을 이용한다.

💡코드

k, n, = map(int, input().split()) # k : 이미 가진 랜선개수 / n : 필요한 랜선개수
lans = []
for i in range(k):
    lans.append(int(input()))

left = 1
right = max(lans)

while left <= right:
    cnt = 0
    mid = (left+right)//2
    for line in lans:
        cnt += line//mid

    # 잘린 개수가 목표치보다 많으면 더 길게 잘라야함
    if cnt >= n:
        left = mid + 1
    else:
        right = mid - 1
print(right)

💡시간복잡도

• O(log N)

💡 틀린 이유

• X

💡 틀린 부분 수정 or 다른 풀이

• X

💡 느낀점 or 기억할정보

• 입력값이 엄청나게 많을 때, 숫자가 지나치게 클 때 이분탐색을 고려한다.