[백준] 2805 나무자르기 파이썬 풀이 (이분탐색)

 

코드(PYPY3)

n, m = map(int, input().split())
tree_list = list(map(int, input().split()))

cut_min = 0
cut_max = max(tree_list)
result_h = 0

while cut_min <= cut_max:
    h = (cut_min + cut_max)//2 # 절단기 높이 선택
    get = 0 # 해당 절단기로 잘라서 가져가는 양

    for tree in tree_list:
        if tree > h:
            get += tree-h

    # 나무를 충분히 가져갔다. 절단기를 올려보자.
    if get >= m:
        result_h = h
        cut_min = h + 1
    else: # 나무가 부족하다. 절단기를 내려야겠다.
        cut_max = h - 1

print(result_h)

풀이

처음에 이해가 안갔던 점은 왜 min을 0부터 시작하는지였다.

나무 높이 중에 가장 작은걸로 하면 안되나 했는데

나무 높이가 다 똑같을 수도 있기때문에 0으로 min을 설정한다.

 

절단기의 높이를 min과 max의 평균으로 하여 계속 높였다 내렸다 한다.

너무 많이 가져갔으면 절단기를 올리고 적게 가져갔으면 절단기를 내려서 나무를 더 벤다.

그리고 여기서 이해가 안가는 점이 왜 min을 h+1로 하고 max를 h-1를 하느냐 였다

왜 h가 아니고 그 위나 아래부터 시작하는가?

그런데 결국 마지막에 min이랑 max가 1 차이나면 무한 루프를 돌게 된다

예를들어 h가 9일때 min이 9가 되고 max가 10이라면

다음h가 min과 max의 평균인데 계속 h가 9가 되는 것이다.

그래서 하나씩 올리고 내려줘야한다

계속 그렇게 만나다가 max랑 min이 똑같아지면 break된다