백준 알고리즘 - [이분 탐색] 나무 자르기

나무자르기 

---

 

 

주의 = '그림이 무성의합니다'

---

문제 - 6줄 요약

1. 마을에 나무 파는곳이 없음. 

2. 나무 M(미터) 필요해서 벌목하기로함.

3. 목재 절단기 구입. 높이값(H) 입력하면 땅에서 H만큼 올라가서
한줄에 나란히 있는 나무 다 ! 자름.

4. 크기가 높이값보다 Down인 나무는 안잘림. 높이값보다 Up 인나무는 잘림
(당연한소리)

예 : (나무 4개 / 20m , 15m, 10m, 17m)   높이값: 15M

답 : 7M만 잘려서 들고감.

5. 무턱대로 자르면 환경이 파괴되니 나무 필요한만큼의 가깝게 자르고싶음.

6. M미터의 나무를 집에 들고가려면 절단기에서 설정할수있는 높이 최대값



입력 첫째줄 1. 나무의 갯수(n) 2. 필요한 M

입력 둘째줄 2. 나무의 높이 (갯수(n)만큼 입력)

 

문제풀이 요령

 

1. 이분 탐색 전조 작업으로 소팅을 통해 나무 배치

2. 절단기의 높이를 기준으로 잘라진 나무들의 합이

 

집에 가져갈 나무 높이(M)보다 작을 경우 절단기의 높이를 늘려 탐색.

그렇지 않으면, 높이를 줄여 탐색한다. (이분탐색)

위와같은 과정을 반복하여 절단기의 최대값을 탐색.

 

코드 -> 

 

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

public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] inputArray = br.readLine().split(" ");  // 띄어 쓰기로 구분(여러가지 숫자넣기위해) 배열에 넣기
        
        int treeCount = Integer.parseInt(inputArray[0]); // 나무의 수 
        int minLengthTree = Integer.parseInt(inputArray[1]); // 적어도 가져가야할 나무의 길이
        
        
        String[] preTreeArray = br.readLine().split(" "); // 위와 동일
        int[] treeArray = new int[treeCount]; // 나무 높이들의 배열
        for(int i=0; i<preTreeArray.length; i++){
            treeArray[i] = Integer.parseInt(preTreeArray[i]);
        }
        Arrays.sort(treeArray); // 오름차순으로 정렬
        int lastInt = treeArray[treeCount-1];
        
        int maxHeight = lastInt; // 톱날의 최대 높이
        int minHeight = 0; // 톱날의 최소 높이
        int middle = 0;    
        
        while(maxHeight >= minHeight){
            middle = (minHeight+maxHeight)/2;
            
            int cutTree = 0; // 톱날로 나무를 잘랐을 때 남은 나무 길이 변수
            long sumCutTree = 0; // 잘라낸 나무 길이들의 합, long을 선언한 이유는 합이 int 범위를 넘어갈 수도 있다.
            
            for(int j=0; j<treeArray.length; j++){
                
                cutTree = treeArray[j] - middle; // 이분탐색으로 적절한 톱날의 높이를 찾아간다. 중간 값으로 나무들을 잘라보고
                                                 // 범위를 좁혀나간다.
                
                if(cutTree <0){
                    cutTree = 0; // 잘린게 없으면 0이기 때문에 마이너스 값은 존재할 수 없다.
                }
                sumCutTree += cutTree;
            }
            
            if(sumCutTree >= minLengthTree){ // 톱으로 잘라낸 나무 길이들의 합이 최소한으로 가져가야되는 나무 길이보다 클 때
                
                minHeight = middle + 1; // 환경을 생각해서 딱 맞춰 잘라가려면 톱날의 높이를 높여서 나무를 조금만 잘라가야 한다.
                
            }else if(sumCutTree < minLengthTree){ // 톱으로 잘라낸 나무 길이들의 합이 최소한으로 가져가야 되는 나무 길이보다 작을 때
                
                maxHeight = middle - 1; // 필요한 나무길이보다 잘라낸 나무 길이들의 합이 작기 때문에 톱날의 높이를 낮춰서 더 길게 베어야 한다.
                
            }
            
        }
        
        System.out.println(maxHeight);    // 톱날의 높이를 설정할 수 있는 높이에서 최대값
    }    
 
}