[BOJ - 이분탐색] 2805번 : 나무자르기 ( python )

 

요즘 정렬이랑 bfs dfs문제만 풀다보니까 다른 유형 문제를 한번도 안풀어서 큰일났다 싶었다. 

이주전쯤에 개념 공부했던거 기반으로 이분탐색, 그리디, 브루트포스, dp까지 비슷한 문제를 풀어보면서 기록하려고 블로그에 왔다. (일반 구현도 해야하지만 급한대로 일단 이친구들 먼저 쭉 해야지)

 

오늘 푼 문제는 백준 2805번 나무자르기!

대표적인 이분탐색 문제이다. 

https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

 

나무가 M만큼 필요하고, 목재절단기를 이용해 나무를 구하는 문제이다.

나무를 절단할 높이를 설정해 나무를 자르고 자른만큼의 합만큼 가져간다고 한다. 

 

나무가 20 15 10 17 이렇게 있으면 높이를 15로 설정했을 때 5 0 0 2 해서 총 7만큼 가져갈수 있다.

 

 

import sys
input= sys.stdin.readline

def binary_search(arr, start, end):
    res = 0
    while start <= end:
        mid = (start+end) // 2
        total = 0
        
        for x in arr:
            if x > mid:
                total+= x- mid
            
        if total < m:
            end = mid-1
        else:
            res = mid
            start = mid +1
    return res
        
n , m = map(int,input().split())
li = list(map(int,input().split()))

r = binary_search(li, 0, max(li))
print(r)

 

 

 

---

binary search의 대표적인 특징

1. 처음과 끝을 정하고

2. 중간값을 구한다음

3. 그 중간값을 이용해 구하고자 하는것을 구하고

4. 처음과 끝값을 바꿔주면서 2-3 반복

 

 

<코드 설명>

 

나는 start 를 0, end 를 max(li)로 주었다.

>> 가장 긴 나무의 길이로 end 설정

 

while start<=end: 라는 반복문은 

start와 end가 값이 계속 변하면서 start가 end보다 값이 커지는 것을 방지하기 위함이다. 

>> start가 end보다 큰건 말이 안되니까

 

while 문 안에서 중간값을 구해주고, 중간값을 나무를 자르는 높이로 생각했을 때 

for x in arr >> 나무길이 리스트인 arr 에서 나무를 한개씩 가져와

자르는 높이보다 크면

나무를 잘라서 total에 더해주었다. 

 

 

우리는 나무가 m 만큼 필요한데 

- total 값이 m보다 작으면 나무가 더 필요하므로 end값을 mid-1 로 바꿔준다. 

>> end 값을 기존보다 작게 함으로써 mid 가 자연스럽게 값이 작아지면 total값은 증가함.

- total 값이 m 보다 클 경우 더 많이 잘라진 것 이다.

우리가 최소 m 만큼 필요한거지 딱 m만큼 잘라야 한다는 조건은 없다. 

그래서 여기에서 일단 res 라는 변수에 mid값을 저장해준다. (최대한 덜 잘랐을 때가 정답이므로)

그리고 start값을 mid +1로 바꿔준다. 

>> start 값을 증가시키면 mid값도 증가

 

while 문이 끝나면 계산이 끝난것이므로 return res 해준다.

 

마지막으로 리턴받은 값을 출력하면 끗!!!!!!!!!!!!