[백준] 2805번 나무 자르기

사용 언어 - Python3

2805번: 나무 자르기 (실버2, 이분 탐색)

문제 ★이분 탐색 문제★

2805번: 나무 자르기

 

 

정답

시작/끝/중간값을 선언하여 중간값과 같을때까지 범위를 줄이는 이분탐색 문제 !!

(코드 풀이)

1. 변수 선언

나무의 수 n개

나무의 길이 m개

tree는 정렬된 상태로 입력받기

 

2. 이분 탐색 정의

높이가 1 이상, max(tree) 이하 여야 자를 수 있기 때문에, 시작점은 1 , 끝점은 max(tree)로 선언한다.

벌목할 높이는 start, end 범위 안에서 목표치 m과 같아질 때까지 계속 조정된다.

벌목된 나무의 총합을 answer에 추가하는 방식이다.

추가로, 자르려는 mid가 트리값보다 큰 경우에는 answer 값이 마이너스가 되므로 추가하지 않고 넘어간다.

 

3. 출력

이분 탐색은 start <= end 범위를 넘어서면 자동으로 종료된다.

mid 값으로 answer == m이 만족했기 때문!

절단기에 설정할 수 있는 높이의 최댓값을 출력해야하므로, start, mid, end 중에 가장 높은 end를 출력한다.

# 정답 - 이분탐색

n, m = map(int,input().split()) #나무의 수n, 나무의 길이m
tree = sorted(list(map(int,input().split())))

start, end = 1, max(tree)
while start <= end:
    mid = (start+end)//2 #나무높이
    answer = 0 #벌목할 나무의 총합으로 m이 되어야한다
    
    for i in tree:
        if i >= mid :
            answer += i-mid
    if answer >= m:
        start = mid+1
    else:
        end = mid-1
        
print(end)

 

---

레퍼런스

• 정답 깃허브

GitHub - yyeongeun/codingtest: 코딩테스트 공부