백준 2805 나무 자르기 파이썬 문제풀이 (python 이분탐색)

문제 보러가기

 

백준 나무 자르기 파이썬 문제풀이

N개의 나무를 일정한 높이로 잘라서 잘려나간 나무 윗부분을 M길이 이상만큼 가져간다.

 

나무의 높이가 각각 있으면, 높이 H만큼 잘랐을 때 나무마다 잘리는 길이가 다를 것이고

이걸 모두 합했을 때 길이 M을 만족하면서 나무를 낭비하지 않는 높이 H의 최대값을 구하는 문제이다.

 

그러면 높이 H를 최소길이와 최대길이 사이에서 탐색하는 문제가 된다.

탐색의 시간을 줄이기 위해서 mid를 이용하는 이분탐색을 사용할 것이다.

 

나무 높이의 start를 s, end를 e라고 하면

s=0이고, e는 가장 높은 나무의 높이이다.

 

mid 높이를 한 번 결정하고 잘라본 다음 잘린 나무 길이들이 합을 sum이라고 하자.

sum이 필요한 길이 M보다 크면 높이를 높여야하니 s를 업데이트하고

sum이 M보다 작으면 높이를 낮추어야하니 e를 업데이트한다.

 

반복 조건은 s < e일 때까지 돌린다.

 

n,m = map(int,input().split())
trees = list(map(int,input().split()))
trees.sort()
s=0
e=trees[n-1]
mid = 0
while s < e:
    mid = (s+e)//2
    # mid 높이로 잘라보기
    sum = 0
    for tr in trees:
        if tr > mid: # 잘리는 부분 있음
            sum += tr-mid
    # 조건 체크
    if sum == m:
        break
    elif sum > m:
        s = mid+1
    else:
        e = mid-1
print(mid)

이렇게 코드를 짜봤지만

틀렸다. 

 

정답코드

n,m = map(int,input().split())
trees = list(map(int,input().split()))
trees.sort()
s=0
e=trees[n-1]
mid = 0
while s <= e:
    mid = (s+e)//2
    # mid 높이로 잘라보기
    sum = 0
    for tr in trees:
        if tr > mid: # 잘리는 부분 있음
            sum += tr-mid
    # 조건 체크
    if sum >= m:
        s = mid+1
    else:
        e = mid-1
print(e)

일단 조건 체크 부분에서 같은 경우와 m보다 sum이 큰 경우를 분리하지 않는다.

또 반복 조건도 s와 e가 교차될 때까지이므로 같은 경우도 포함해야한다.

 

그리고 중요한 것은 mid값으로 일치하는걸 구하는게 아니라

높이 최대값을 구하는 것이므로 

 

최종적으로 구하게 되는 값은 mid가 아니라 end e일 것이다. 

sum와 m이 같아지지 않는 경우가 생긴다면,

sum이 m보다는 큰 조건을 만족하면서 가장 큰 높이는 mid가 아니라 e이다.

 

이 부분이 상당히 어려운데.

만족하는 높이가 여러개이고 그중 가장 높은 값을 선택하는 과정이다.

 

만족하는 높이가 여러개이면

위 그림처럼 이분탐색을 하면서 

 

마지막에는 만족하는 높이의 최대값에 e가 위치하고,

만족하는 높이의 최대값 +1에 s와 mid가 존재하게 된다.