[백준] 2805번 나무자르기 - 파이썬

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

2805번: 나무 자르기

---

sol) 사용한 알고리즘 : 이분탐색 

 

💡문제이해 

나무의 높이 : 20 15 10 17 , 최소 집으로 가져가려고 하는 나무의 길이 : 7 

20-15 + 17-15 = 7 ⇒ 설정할 수 있는 최대 높이 : 15 

 

🤔 이분탐색을 이용해 설정할 수 있는 최대 높이 찾기 

 

 

1. 나무의 수 (n) , 집으로 가져오려고 하는 최소 나무의 길이 (m) 와 나무들의 길이(forest)

 

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

 

2.  처음 과 끝 point 설정 

s = 0 
e = max(forest)

 

3. 처음과 끝 점이 교차되지 않는 지점까지 가져갈 수 있는 나무의 길이를 계산 

⇒ 만일 최소 나무길이에 만족한다면 처음 point를 mid+1로, 최소 나무길이보다 부족하다면 끝 point를 mid-1로 계산

while e >= s : #e와 s가 교차되지 않는 지점까지 반복
	
    mid = (s+e) //2  #중간 포인트 설정 
    
    wood = 0
    #가져갈 수 있는 나무 길이 계산 
    for tree in forest :
    	if tree >= mid :
        	wood += tree-mid
            
    if wood >= m : #만일 최소 충족을 만족시킨다면 
    	s = mid+1 
   	else :  #만일 최소 충족을 하지 못할 경우
    	e = mid -1

4. 최대 길이를 계산하므로 끝 point 출력 

print(e)

 

5. 전체코드 

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


s = 0 
e = max(forest)

while e >= s :

    mid = (s+e) // 2 

   
    wood = 0
    for tree in forest :
        if tree >= mid :
            wood += tree-mid 
    
    if wood >= m : 
        s = mid +1 
    else :
        e = mid -1 

print(e)