랜선 자르기

나무자르기문제와 굉장히 유사한 문제이다.

먼저 자르는 랜선의 길이는 (소유하고 있는 모든 랜선을 합한 길이 // 랜선의 총 개수)보다 클 수 없다. 따라서, 이분탐색을 할 때 초기의 최소 길이는 0 그리고 최대 길이는 위와 같이 정한다.

또한, 필요한 랜선의 개수 N과 비교하기 위해 cut함수를 만들었다.

cut에 x를 입력하면, 소유하고 있는 랜선으로 만들 수 있는 x길이의 랜선의 수를 return 한다. 이 값을 N과 비교하며 이분탐색을 진행한다.

Plus

가지고 있는 랜선 길이의 총 합이 1인 경우, 위의 알고리즘으로 풀게 되면 error가 발생한다.

총 합이 1인 경우 MAX_LAN=1, MIN_LAN=0이 되어 mid=(1+0)//2=0이고, 이 값을 cut 함수에 넣으면, 각각의 랜선을 0으로 나누게 된다.

또한, 총 합이 1인 경우 문제에서 답이 없는 입력을 넣지는 않음으로, 반드시 답은 1이 될 수 밖에 없다.

따라서, 이 경우에는 1을 출력하고 끝내면 된다.

CODE

import sys
read = sys.stdin.readline

k, n = map(int, read().split())
LAN = list(int(read()) for _ in range(k))
#자르는 랜선의 최대 길이는 모든 랜선을 합해 랜선의 개수로 나눈 값과 같다.
MAX_LAN = sum(LAN)//n
MIN_LAN = 0
#랜선 길이의 총합이 1이라면, 1을 출력하고 종료한다.
#불가능한 경우는 주어지지 않음으로.
if MAX_LAN == 1:
    print(1)
    sys.exit()
#가지고 있는 랜선으로부터 x길이의 랜선이 몇개 나올 수 있는지 구한다.
def cut(x):
    tot = 0
    for l in LAN:
        tot += l//x
    return tot
#이분 탐색
answer = 0
while MAX_LAN >= MIN_LAN:
    mid = (MIN_LAN+MAX_LAN)//2
    if cut(mid) >= n:
        #이때, answer가 mid보다 크면 while문을 탈출한다.
        answer = max(answer, mid)
        if answer == mid:
            MIN_LAN = mid+1
        else:
            break
    else:
        MAX_LAN = mid-1
print(answer)


틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]