이분탐색을 언제 사용할 것인가

이분탐색을 사용하면 내가 원하는 값을 logN의 횟수로 알아낼 수 있다.

중요한 포인트는 전제조건 밑 범위에 있는데
1. 원하는 값이 lo, hi 안에 들어갈 수 있도록 범위를 잘 설정해야하고
2. 찾으려는 값이 오름차순 혹은 내림차순으로 정렬되어있어야 한다.

오늘 백준 평범한 배낭2을 풀면서 적절한 값 k을 찾기 위해서 이분탐색을 이용해 수행할 생각이였는데 실패했다.

N, M = map(int, input().split())

# weight, value, k 순서대로
arr = []
for _ in range(N):
    arr.append(list(map(int, input().split())))
arr.sort(key=lambda x: x[1] / x[0], reverse=True)

dp = [0] * (M + 1)


def check(weight, mid, w, v, k):
    # mid: 적절하다고 판단되는 물건의 개수
    # w: weight, v: value,
    return mid <= k and weight - mid * w >= 0 and dp[weight] < dp[weight - mid * w] + mid * v


# main function
for w, v, k in arr:
    for weight in range(M, 0, -1):
        if weight < w:
            break

        lo = 0
        hi = 10_001

        while lo + 1 < hi:
            mid = (lo + hi) // 2

            if check(weight, mid, w, v, k):
                lo = mid
            else:
                hi = mid
            # lo에 적절한 k 값이 들어가 있음

        # print(f' weight: {weight} / lo : {lo}')
        dp[weight] = max(dp[weight], dp[weight - lo * w] + lo * v)




print(dp[-1])

해당 코드를 보면 최상단에 sort를 수행하면서 이분탐색 중 나타나는 mid의 예상출력 값이 일정하게 정렬되도록 유도했지만 실패했다.

어려웠다.