[백준] 2805번

문제출처: https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

 

나무의 수와 벌목해서 가져가고싶은 나무의 길이가 제시된다.

이때 최소한으로 자르기 위한 톱의 높이가 최대값을 구하는 문제다.

​

우선 이분 탐색은 쉽게 말해 예/아니오로 답하는 게임과도 같다고 할수있다.

극단적으로 표현한 MBTI로 나누자면,

당신은 사교성이 넘칩니까?

Yes -> E / No -> I

이렇게 이분적인 사고로 나눈다는 것이다.

그걸 코드로 구현하면 된다.

​

시작은 1, 끝은 가장 긴 나무의 길이로 선정하고 시작한다.

그리고 위와 같이 이분탐색을 한다.

자른 나무 길이 총합이 목표치보다 높거나 같습니까?

Yes -> start 값을 mid+1값으로 바꿔준다.

No -> end 값을 mid-1값으로 바꿔준다.

​

언제까지고 이 반복문만 계속 돌릴 순 없다. 탈출해서 최종값을 구해야한다.

반복문을 멈추는 시점은 start 값이 end 값보다 커질 때이다.

빠져나온 이후의 최종 end 값을 출력으로 넣어주면 된다.