[백준] 2805번 나무 자르기 _ Node.js

문제

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

2805번: 나무 자르기

---

문제 풀이

 처음 해당 문제를 풀 때 간단한 문제로 판단하여 완전 탐색을 시작하였다. 하지만 해당 문제의 나무의 개수는 최대 100만개, 길이는 2억이 넘는다. 그렇기에 완전 탐색으로 풀이하였을 때 시간초과가 나왔다.

 

해당 문제는 이진 탐색으로 풀면 시간초과를 해결할 수 있다.

 

나무를 자르는 기계로 자를 수 있는 높이는 최대는 가장 긴 나무의 길이, 최소는 0이다. 그렇기에 최대, 최소를 각각 가장 긴나무의 길이, 0으로 설정한다,

 

이 후 이 둘의 중간 값인 mid의 길이로 설정하여 나무를 자르면 얼마나 나오는지 확인한다.

 이 때 잘린 나무의 길이가 필요한 나무의 길이보다 길 경우 해당 길이보다 높은 높이로 잘라야한다.  그렇기 때문에 최소 길이를 mid + 1로 대체한다.

 반대로 잘린 나무의 길이가 필요한 나무의 길이보다 짧다면 해당 길이보다 낮은 높이로 잘라야 한다. 그렇기 때문에 최대 길이는 mid -1로 설정해준다.

 

해당 과정을 반복하면 최대와 최소가 같아지는 순간이 오고 해당 값이 결과 값이다. 

 

아래는 예제 입력 1을 그림으로 구현한 모습이다.

 

실행 1 ) 0과 20의 중간인 10을 기준으로 기계를 작동 -> 잘린 나무의 길이가 17보다 크다. -> 최소 = 중간 + 1

 

실행 2 ) 11과 20의 중간인 15을 기준으로 기계를 작동 -> 잘린 나무의 길이가 17보다 작다. -> 최대 = 중간 -1

해당 과정을 계속 진행하면 아래와 같은 결과가 나온다

 

이처럼 이진 탐색으로 진행하면 시간 복잡도가 N(M)에서 N(log2(M))으로 줄어든다. 이렇기에 원하는 값을 찾을 때 이진 탐색을 사용하여보자.