문제

나무 자르기

풀이

이 문제 에서는 나무를 잘라 가져가려고 하는 나무의 총 합 길이가 m이다 이 길이는 커도 안되고 적어도 안된다. 그저 m의 나무 길이가 남으면서도 가장 나무를 길게 남길수 있는 방법을 찾는 것이다.

		int min = 0;
        while (min < max) {
            int mid = (min + max) / 2;
            long sum = 0;
            for (int tree : arr) {
                if (tree - mid > 0) {
                    sum += tree - mid;
                }
            }

            if (sum < m) {
                max = mid;
            } else {
                min = mid + 1;
            }
        }
        System.out.println(min - 1);

중간값으로 일단 나누고 남은 값을 다 더해준 값이 남은 나무의 길이(sum) 이므로 이값이 m 보다 작을때는 큰 값을 나무의 자르는 길이를 늘려야 하기 때문에 max의 값을 mid에 대입해주고 (자르는 길이를 늘려야 가져가는 값이 적어짐) 반대의 경우 자르는 길이를 작게 해서 min 값을 중간값에 설정 해준다 (자르는 길이를 작게 하면 가져가는 값이 많아짐)
그래서 최종적으로 min 값을 출력해주어야 한다.
아직 응용하기가 어려웠다. 다른 이분탐색 문제를 더 풀어봐야할것같다.

전체 코드

전체 코드