1654 랜선자르기 파이썬

실3

같은 이분탐색 내용인 랜선자르기 문제를 풀어보았다.

이전에 풀었던 EKO(나무자르기) 문제와 같은 유형의 문제였다.

다만 달랐던 것은 탐색값이 target과 같아지는 것이 최대로 자를 수 있는 랜선을 의미하는 것이 아니라는 것이다.

def binary_search(target, start, end):
    mid = (start + end) // 2
    if start > end:
        return end

    if divide(mid) >= target:
        # 너무 작게 자른것, 더 크게 잘라야 함
        return binary_search(target, mid+1, end)
    else:
        return binary_search(target, start, mid-1)

이분탐색을 구현하는 부분을 보면 이전에는

if cut(mid) == target:

을 처리 해주는 부분이 있었는데, 그 때는 cutting을 해서 나온 값이 target과 같다면 그것이 최대값이라는 보장이 있었기 때문인데,

이번 문제는 나눗셈의 몫을 모두 더하는 문제이기 때문에, target과 일치한다고 해서 그 target값이 최대로 자를 수 있는 랜선길이라는 것을 보장할 수가 없다.

즉, 최대값은 자를 수 있는 랜선 개수가 변화하는 그 시점의 랜선 길이이다.

그러므로 target과 같다고 바로 리턴해버리는 것이 아니라, target보다 크거나 같은 경우에 계속해서 탐색을 진행하는 것을 통해 mid 값을 계속해서 올려주어야 한다. 결국 start와 end가 만나는 시점에 return을 수행하게 된다.

# 최대 랜선의 길이를 탐색
# 가져온 랜선의 최대 길이를 구해서
# 그 사이에서 이분탐색

k, n = map(int, input().split(" "))
arr = []
for i in range(k):
    arr.append(int(input()))

def solution():
    # 나누기를 해서 몫들을 모두 합침.
    print(binary_search(n, 1, max(arr)))



def binary_search(target, start, end):
    mid = (start + end) // 2
    if start > end:
        return end

    if divide(mid) >= target:
        # 너무 작게 자른것, 더 크게 잘라야 함
        return binary_search(target, mid+1, end)
    else:
        return binary_search(target, start, mid-1)

def divide(value):
    sum = 0
    for i in arr:
        if i >= value:
            sum += i // value
    return sum


solution()

전체 코드