[알고리즘/이분 탐색] 2805번 : 나무 자르기 - python

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

2805번: 나무 자르기

 

---

• 문제
• 소요시간: 22분 실패

---

• 설계하기(접근방법) 

1. 입력받기

나무의 길이를 입력받는다

 

2. 구현하기

이분 탐색 문제를 풀어보았다

 

start 높이를 1로 가정하고

end는 모든 나무 높이의 합(최대치)로 한다

 

start, end의 중간값으로

나무를 잘라본 후

잘린 결과를 더해 나간다

 

만약 총 합이 target보다 크다면

start크기를 mid + 1로  늘려주어서

다음 mid를 늘려준다

그렇다면 나무가 덜 잘리게 된다

 

반대라면

end를 mid -1로 줄여주어서

다음 mid를 줄인다

그렇다면 나무가 더 잘린

3. 출력하기

 

 

---

• 코드(출력)

n , target = map(int,input().split())
tree = list(map(int,input().split()))

start, end = 1, sum(tree)

while start  <= end:
    cnt = 0
    mid = (start + end) // 2
    for i in tree :
        if i > mid:
            cnt += i - mid 
    if cnt >= target:
        start = mid + 1
    else:
        end = mid - 1
    
print(end)

---

• 얻어갈 부분

1. 이분탐색에 대해서 배웠다