백준, 나무 자르기(2805, java)

문제 설명

상근이는 나무를 자르려고 한다. 이때 상근이는 환경에 관심이 많아 필요한 만큼의 나무만 들고가려고 한다. 이때 가질 수 있는 톱의 최대 높이를 구하는 문제이다.

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

2805번: 나무 자르기

간단히 설명하자면 상근이가 나무를 자르는데, 잘린 나무의 값과 주어진 M의 값의 오차가(무조건 양수) 최소가 되게 하는 높이를 구하는 문제이다.

문제 풀이

이진탐색

자를 높이를 이진탐색으로 찾는 문제이다.

이진 탐색에서는 범위가 중요한데, 나는 초반에는 시작 범위를 주어진 나무 높이 중 제일 작은 것으로 해주었다. 하지만, 이렇게 해주면 안 되었는데 나무는 제일 작은 나무의 높이보다 더 아래에서 잘릴 수 있기 때문이다.

 

예를 들어서 총 4개의 나무의 길이가 4, 4, 4, 4이고 원하는 나무는 총 16이라고 해보자. 0에서 나무를 자르면 16이라는 값을 얻을 수 있다. 그러나 내가 해줬던 대로 제일 작은 나무 높이로 시작 값을 잡아 버리면 4에서부터 나무를 자른다는 의미기에 답이 나오지 않는다.

 

그렇기에 이진 탐색을 시작하기 전 초기의 왼쪽 값은 0으로 표시를 해줘야 한다.

 

그 다음 이진탐색을 위해 반복문을 돌려준다.

이진탐색에서는 언제나 왼쪽 값이 오른쪽 값보다 작아야 하므로 start < end라는 조건을 넣어준다.

 

범위에서 절반 값인 mid를 잡아준 다음 chek 함수를 이용하여 잘린 나무의 합을 구해준다. 만일 합이 주어진 M보다 작으면 톱의 높이를 낮춰줘야 한다. 그렇지 않고 M보다 크다면? 원하는 만큼은 잘랐으니 그만 둬야 할까? 아니, 톱의 높이를 높여서 범위를 좁혀줘야 한다. 그 이유는 톱의 높이의 최대 값을 알고 싶기 때문이다.

 

나는 upper bound 즉, start가 mid+1이 되도록 했다. 그러므로 우리가 원하는 값은 start-1이 된다. 이진탐색은 원하는 값을 계속해서 좁혀나가는 것이기에 만일 원하는 값이 나왔을 경우 start+1이 되면서 start+1 >= end로 반복문을 탈출한다. 그러므로 답은 start-1이 되는 것이다.

 

참고로 자른 나무의 합이 M이 될 때도 start=mid+1이 되도록 했는데, 그 이유는 위에도 나와있듯이 범위를 아주 좁게 좁혀서 start+1이 end보다 클 경우 탈출하는 조건에 맞춰줘야 하기 때문이다.

 

혹시 몰라서 예제 1을 이용해 실행 과정을 밑에 풀어서 작성했다.

실행 과정

[10, 15, 17, 20], M = 7

 

start: 0, end: 20, mid: (0+20)/2 = 10, left: 5 + 17 + 10 = 32

M < 32 이므로 높이를 높인다.

 

start: 11, end: 20, mid: (11+20)/2 = 15, left: 2 + 5 = 7

M == 7이므로 탈출할까?

아니, 이진탐색으로 계속해서 범위를 좁혀 나가 start >= end인 상황을 만들어 준다.

 

start: 16, end: 20, mid: (16+20)/2 = 18, left: 2

M > 2 이므로 높이를 낮춘다.

 

start: 16, end: 18, mid (16+18)/2 = 17, left: 3

M>3 이므로 높이를 낮춘다.

 

start: 16, end: 17, mid (16+17) = 16, left: 6

M>6 이므로 높이를 낮춘다.

 

start: 16, end: 16 

탈출 상황이다!

정답 16-1로 15가 된다.

코드

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.*;

public class Main {
    public static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input1 = br.readLine().split(" ");
        int N = Integer.parseInt(input1[0]);
        long M = Long.parseLong(input1[1]);

        long[] trees = new long[N];
        String[] input2 = br.readLine().split(" ");
        for(int i=0; i < trees.length; i++){
            trees[i] = Long.parseLong(input2[i]);
        }

        Arrays.sort(trees);
        long start = 0;
        long end = trees[N-1];
        long mid = 0;

        while(start < end){

            mid = (start+end)/2;
            long tmp = check(trees, mid);

            if(tmp < M){
                //잘린 나무가 원하는 것보다 작다 -> 더 잘라야 한다 -> 높이를 낮춘다.
                end = mid;
            }else{
                //잘린 나무가 원하는 것보다 많다 -> 덜 잘라야 한다 -> 높이를 높인다.
                start = mid+1;
            }
        }

        System.out.println(start-1);

    }

    public static long check(long[] trees, long length){

        long sum = 0;
        for(long tree : trees){
            if(length < tree){
                sum += (tree-length);
            }
        }

        return sum;
    }


}