[JAVA] 백준 2805 나무 자르기

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

2805번: 나무 자르기

 

- 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다.

정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재 전달기를 이용해서 나무를 구할 것이다. 

 

- 목재 절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 전달해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 

 

- 예를 들어, 한 줄에 연속해있는 나무의 높이가 20,15,10,17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15,15,10,15가 될 것이고 상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. (총 7미터를 집에 들고 간다) 절단기에 설정할 수 있는 높이는 양의 정수 또는 0이다.

 

- 상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성 

 

 

문제 풀이 

 

- 매개변수 탐색으로 조건이 변하는 부분의 최대값 탐색

- 이진 탐색은 탐색 도중에 원하는 값이 발견되면 바로 종료되지만, 매개변수 탐색은 결국 탐색할 중간값(매개변수)이 존재하지 않는 범위까지 탐색하게 됨 

 

매개변수 

 

- 절단기에 설정할 수 있는 높이의 최댓값 x

- x의 길이는 검사범위에서의 중간값(mid)이고, 결정함수의 결과에 따라서 x를 늘리고 줄이면서 확인 

 

결정함수 

 

- N개의 나무를 x만큼 잘랐을 때, 그 합이 M개가 되어야 한다"로 설정

- 위의 조건을 만족하면 true를 , 만족하지 않으면 false를 반환 

 

 

정답 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    static int N,M;
    static int Tree[];
    static long max,min,mid;
    
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st;
        st= new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); //나무의 수 
        M = Integer.parseInt(st.nextToken()); //나무의 길이 
        
        Tree = new int[N];
        
        max = Long.MIN_VALUE;
        min =0;
        
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++)
        {
            Tree[i] = Integer.parseInt(st.nextToken());
            max = Math.max(Tree[i],max);
        }
        max++;
        
        while(min<max)
        {
            mid = (min+max)/2;
            
            long sum = 0;
            
            for(int i=0; i<N; i++)
            {
                if(Tree[i]-mid>0)
                {
                    sum+=(Tree[i]-mid);
                }
            }
            
            if(sum<M)
            {
                max=mid;
            }
            else
            {
                min=mid+1;
            }
        }
        
        bw.write(String.valueOf(min-1));
        
        bw.flush();
        bw.close();
        br.close();
        
    }
    
}