[백준] 1654 랜선 자르기

📌문제 링크

링크텍스트

💡 문제 풀이

2805 나무 자르기 문제와 동일하게 랜선의 길이를 범위로 해서 이진탐색으로 풀이했다.

1. 0부터 랜선의 최대 길이까지를 이진 탐색의 범위로 설정한다.
(start = 0, end = max(line))

2. mid = (start + end) // 2 의 길이로 랜선을 잘랐을 때 랜선의 개수를 계산한다.
(각 랜선의 길이에서 mid만큼 나눈 값을 모두 더함)

3. 랜선의 개수가 부족한 경우 자를 랜선의 길이를 줄인다.
(if total < m: end = mid - 1)

4. 랜선의 개수가 충분한 경우 절단기의 높이를 높인다.
이 때, 랜선의 개수가 n보다 커도 n개를 만들긴 했기 때문에 결과값인 result에 mid 값을 저장한다.
(if total >= m : start = mid + 1, result = mid)

📋코드

k, n = map(int, input().split())
line = list()

for i in range(k):
    line.append(int(input()))  # append 시간복잡도 O(1)

# 이진 탐색을 위한 시작점과 끝점 설정
start = 0
end = max(line)

result = 0
while start <= end:
    total = 0
    mid = (start + end) // 2

    if mid < 1:
        mid = 1

    for x in line:
        # 잘랐을 때의 랜선의 개수 계산
        if x >= mid:
            total += x // mid
    # 랜선의 개수가 부족한 경우 자를 랜선의 길이를 줄임
    if total < n:
        end = mid - 1
    # 랜선의 개수가 n보다 클 경우 자를 랜선의 길이를 높임
    else:
        result = mid  # 더 많이 만들었어도 n개 만든거니까 일단 기록
        start = mid + 1

print(result)