[BOJ] 백준 2805 나무 자르기 (JAVA)

[BOJ] 백준 2805 나무 자르기 (JAVA)Algorithm/- Baekjoon2023. 12. 29. 06:46@Koben

Table of Contents

📑 문제

입력되는 나무의 양(N)은 1 ≤ N ≤ 1,000,000, 즉 O(n^2)을 가지는 알고리즘이 아닌 O(N)또는 더 빠른 알고리즘을 사용해야 한다.

만약 M미터의 나무를 가져가기 위해서 1~1,000,000까지의 높이를 나이브하게 대입하면서 답을 구할 수 있지만,

최악일 경우는 시간초과가 나게 된다. 즉 모든 경우를 대입하는 방식은 이 문제에서는 틀리다!

큰 범위에서 해당값을 하나를 구해야 한다, 이진탐색(Binary Search)을 통해서 해당값을 구할 수 있다.

가정을 해보자, 만약 1 ~ 7까지에서 6을 구해야 한다면 이진탐색은 이렇게 작동한다.

일단 이진탐색을 하기 위해선 최솟값, 중간값(mid), 최댓값을 구해야 한다.

처음에는 중간값인 4를 탐색한다, 하지만 답인 "6"이 아니면서 중간값인 "4" 보다 크기 때문에 범위를 5~7로 조정한다.

이 과정에서 최솟값을 (mid+1) 값으로 갱신한다.

최솟값은 mid +1 = 5가 되었고, 최솟값과 최댓값의 중간값인 "6"을 탐색하고 종료한다.

즉 위의 구조를 반복해서 범위를 2로 나누면서 "답이 존재하는 범위를 줄여가며 탐색한다"

위 문제는 자를 나무 높이를 지정하고, 남은 나무량과 M에 비례해서 이진탐색을 한다면 시간복잡도는 O(log n) 이므로

O(N) 보다 더 빠르게 문제를 해결할 수 있다.

중간값은 "(최솟값 + 최댓값) / 2" 으로 구할 수 있다. 이진탐색으로 범위/2 씩 하면서 답이 존재 가능한 범위를 줄여나간다!

코드에 주석을 달아놨으니 천천히 읽어보면 이분탐색이 어떤 식으로 동작하는지 잘 알 수 있을 것이라 생각한다.

한번 그림으로 그려가면서 이해하는 것을 추천한다!

이진탐색에 대해서 배우게 된 문제였다, 개념은 알고 있었지만 코드로 작성하는 것과 안 하는 것은 차이가 되게

컸던 것 같다. 그래도 이론적으로 알고 있었기 때문에 이해하는데 크게 어렵지 않았다.

이분탐색을 잘 배워놓고 활용할 수 있을 정도로 손에 익게 연습하겠다.