백준 2805 나무 자르기 - 이분 탐색

2805번: 나무 자르기 (acmicpc.net)

2805번: 나무 자르기

이분탐색으로 푼 첫 문제였다.

<이분탐색으로 풀기 전 코드>

N, M = map(int, input().split())
lst = list(map(int, input().split()))
for j in range(max(lst) - 1, 0, -1):
    new_lst = [lst[i] - j if lst[i] - j > 0 else 0 for i in range(len(lst))]
    if sum(new_lst) >= M :
        print(j)
        break

그 때 그 때 뺄셈을 한 값으로 리스트를 초기화해가면서 요구사항을 충족할 때까지 for문을 돌리는 코드인데..

문제는 list의 크기가 1000000까지 될 수 있다는 것이다.

그 때는 for문을 100번해야되고 게다가 이중 포문이므로 시간복잡도가 끝내주게 커지게 됨.

따라서 이제는 진짜 이분 탐색을 쓸 때이다.

이분탐색의 시간복잡도는 O(log2N)로, 

원하는 값이 나올 때까지 계속 반씩 쪼개 가면서 답과 근접해지므로 기존 코드의 시간복잡도인 O(N^2)보다 훨씬 나은 셈

import sys
N, M = map(int, input().split())
lst = list(map(int, sys.stdin.readline().split()))
start, end = 1, max(lst)
while start <= end:
    mid = (start + end) // 2
    cnt = 0
    for i in lst:
        if i > mid:
            cnt += i - mid
    if cnt >= M:
        start = mid + 1
    else:
        end = mid - 1
print(end)

문제 해석) N개의 tree가 있을 때 각각 똑같은 길이만큼 잘라서 전체 길이의 합이 M이 되게 하눈 문제.

우리가 이분탐색으로 최종적으로 근접하게 되어야 하는 값은 Mid이고, 이는 자르는 나무의 크기, 즉 정답이다.

나무의 길이가 mid 보다 클 때(다른 경우는 0이 되어야 하므로 합하면 안 됨) cnt,즉 M이 되어야하는 값을 구해주고 이를 M과 비교해서 우리가 구해야하는 M보다 크면 start를 mid보다 크게, 작으면 end를 mid보다 작게 만들면서 범위를 좁혀간다.

start와 end가 같아질 때까지 이를 반복한다.

이분 탐색은 그 형태를 잘 알고 start,end를 몇으로 설정할지, 우리가 구해야 하는 값을 제대로 mid로 선택하는 것 등이 중요한 것 같다.

앞으로도 많이 풀어보고 익히자.