이진탐색 유형(알고리즘, Python)

나무자르기_내접근

def binary_search(val, start, end):
    while start <= end:
        mid = (start + end)//2
        mid_val = sum([logs[i] - mid for i in range(len(logs)) if logs[i]>=mid])

        if mid_val == val:
            # print('==')
            return mid

        if start == mid:
            # print(start, mid, end)
            if mid_val > val:
                # print(1)
                a = mid+1
                if val < sum([logs[i] - a for i in range(len(logs)) if logs[i]>=a]):
                    return a
                else:
                    return mid
            elif mid_val < val:
                # print(2)
                a = mid-1
                if val < sum([logs[i] - a for i in range(len(logs)) if logs[i]>=a]):
                    return a
                else:
                    return mid-2

        if mid_val < val:
            end = mid - 1
        elif mid_val > val:
            start = mid + 1


import sys
n, m = map(int, input().split())
logs = list(map(int, sys.stdin.readline().rstrip().split()))
print(binary_search(m, 0, max(logs)-1))

• 내가 접근한 방식은 이진탐색을 하면서 최종원소 1개만 남을때는 무조건 start==mid 가 되기 때문에 최종원소 1개만 남았을 때 이 원소(길이)로 잘랐을때 총합길이가 맞춰야하는 길이와 비교해서 최종원소-1 or 최종원소+1 을 하는 방법이다.

• 근데 틀렸다고 한다.

• 왤까????

나무자르기_이코테접근

def binary_search(val, start, end):
    while start <= end:
        mid = (start + end)//2
        mid_val = sum([logs[i] - mid for i in range(len(logs)) if logs[i]>=mid])

        if mid_val == val:
            return mid
        elif mid_val < val:
            end = mid - 1
        elif mid_val > val:
            result = mid
            start = mid + 1
    return result

import sys
n, m = map(int, input().split())
logs = list(map(int, sys.stdin.readline().rstrip().split()))
print(binary_search(m, 0, max(logs)-1))

• 원하는 길이보다 큰경우에 그 값을 계속 저장해놓으면서 최종적으로 원하는 길이보다 큰것을 만족한 길이를 리턴한다.

• 이 솔루션도 python3로는 통과를 못한다;; pypy3는 된당

• 일단 이 솔루션을 외웠다.
  엄청 많는 범위를 탐색하는 경우 + 찾는 값이 그 범위안에 없을 수도 있고 + 찾으려는 값과 가장 가까우면서 크거나 작은 값을 찾아야하는 경우에 이 솔루션을 떠올릴 것이다.