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

이진탐색 기초!

📑 문제

백준 2805번 나무 자르기

---

🌱 아이디어

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

 

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

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

 

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

 

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

(1)

 

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

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

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

(2)

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

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

 

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

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

---

🌱 코드 및 풀이

	public class Main {
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine(), " ");
	int N = Integer.parseInt(st.nextToken());
	int M = Integer.parseInt(st.nextToken());
	int max = 0;
	int[] arr1 = new int[N];
	st = new StringTokenizer(br.readLine(), " ");
	for (int i = 0; i < N; i++) {
	arr1[i] = Integer.parseInt(st.nextToken());
	max = Math.max(max, arr1[i]);
	}
	// 이분탐색 범위 설정
	int left = 0, right = max;
	while (left <= right) {
	// 이분탐색 중간값 구하기
	// ex. 50~100, 중간값은 (50+100)/2 = 75 이다.
	int mid = (left + right)/ 2;
	long sum = 0;
	for (int i = 0; i < N; i++) {
	// 중간값으로 나무 자르기
	int num = arr1[i] - mid;
	if (num > 0) {
	sum += num;
	}
	}
	// 이분탐색 알고리즘, 시간복잡도때문에 완탐은 불가능 하다.
	if (sum < M) {
	// 자른 나무길이보다 M이 크다면, 너무 크게 잘랐기 때문에 범위를 좁힌다 (최댓값 줄이기)
	right = mid-1;
	} else {
	// 자른 나무길이보다 M이 작거나 같다면, 너무 작게 잘랐기 때문에 범위를 좁힌다 (최솟값 키우기)
	left = mid + 1;
	}
	}
	// else문으로 작거나 "같다"까지 연산해줬기 때문에 +1 부분을 다시 빼준다
	System.out.println(left-1);
	}
	}

view raw 나무 자르기.java hosted with ❤ by GitHub

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

 

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

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

---

🌱 느낀 점

(시간초과만 8번했다;;;)

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

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

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