[백준] 2805 - 나무 자르기

Solved.ac Class 완전정복 프로젝트

Class : 2 ~ 2 ++

 

 

---

링크

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미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

입력
첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

출력
적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

 

접근방법

 1654(랜선 자르기) 문제와 유사한 문제다. 문제는 최소 M이상을 만족할 수 있는 H 중에서 가장 큰 값을 결과로 출력하는 것을 요구한다. 범위가 매우 다양하므로, 이 문제 역시 이진 탐색으로 접근해야 한다. 문제의 범위가 매우 큰 것을 인지하고 풀이로 접근하자. 이 문제가 이진 탐색을 요구하는지 모르겠다면, 1654 풀이 포스팅을 참고하길 바란다.

[백준] 1654 - 랜선 자르기 JAVA 재귀함수를 이용한 이진탐색

 

 

실패 원인

 문제를 보고 N과 M이 int 범위 안에 들어왔기 때문에, 너무나도 안 힐 하게 int형 자료형을 사용하였다. 나무 길이 M은 int형 범위 안에 들어가지만, 탐색 과정에서 오버플로우가 발생하는 상황을 간과했기에 벌어진 실수였다. 별의별 수정을 해도 안돼서, 혹시나 해서 마지막으로 바꾼 자료형이 원인이었다. (이럴 때마다 눈물이 난다.ㅠㅠ) 항상 자료형에 대해 생각하는 습관이 필요해진 것을 느끼게 한 문제이다.

 

 

풀이

 두 가지 방법으로 풀이를 제시한다.

1. 재귀 형식의 풀이 방법

 이진 탐색 함수를 만들어 재귀 호출을 통해 결과를 구한다. 아마 이 문제를 어렵게 느꼈다면, M이상을 만족하는 최대 H를 만드는 조건을 구현하는 것이 어려웠던 것일 수도 있다. H가 높아질수록, 잘리고 남은 길이의 합인 M은 줄어들 수밖에 없다. 그러므로, M을 만족할 만큼 딱 맞게 자르거나, 혹은 그렇게 알맞게 떨어지지 않는다면, M이상의 길이를 만드는 H 중 가장 큰 녀석이 M과 가장 가깝다. 

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Main test = new Main();
    }

    public Main() {
        Scanner sc = new Scanner(System.in);
        int cnt = sc.nextInt();
        int M = sc.nextInt();

        int[] lumbers = new int[cnt];
        for (int i = 0; i < cnt; i++) {
            lumbers[i] = sc.nextInt();
        }

        //반환값은 size 이어야함
        System.out.println(solution(lumbers, M));
    }

    public long solution(int[] lumbers, int M) {
        //이진 탐색을 위한 정렬
        Arrays.sort(lumbers);
        long result = binary_search(lumbers, 1, lumbers[lumbers.length - 1], M, 0);

        return result;
    }


//    output : 절단해서 최소 M이상을 가져올수 있는 최대 H의 길이
//    조건 처리 기준 1 ~ Max Value 사이를 이분탐색하여, 탐색한 값이 M이상 길이를 가져다 줄때 H의 최대 길이
    public long binary_search(int[] lumbers, int start, int end, int M, long preH) {

         //넘어가면 승계받은 값을 반환한다.
        if(start > end){
            return preH;
        }

        int currentH = (start + end) / 2;

        long currentSize = sumCuttedLumbers(lumbers, currentH);
        long nextH;
        
        //currentSize가 작다 = H가 너무 크다 -> 크기를 줄여야한다.
        if (currentSize < M) {
            nextH= binary_search(lumbers, start, currentH-1, M, preH);


        } else {
            //currentSize가 크거나 같다. = H가 작거나 같다. -> 크기를 늘려야한다.
            //이 구간에 있는 current_H는 일단 M을 만족한다.
            //따라서 current_H와 외부에서 넘어온 preH값을 비교하여 큰 녀석을 계속 승계받는다.
            nextH= binary_search(lumbers, currentH+1, end, M, currentH > preH ? currentH: preH);


        }
        
        return nextH > preH ? nextH : preH;

    }


    //output 해당 H로 잘랐을 때, 잘린 목재 길이의 합
    public long sumCuttedLumbers(int[] lumbers, long H) {
        long result = 0;
        for (int lumber : lumbers) {
            if (lumber - H < 0) {
                continue;
            }
            result += (lumber - H);
        }
        return result;
    }

}

 

2. 반복문 형식

 위의 코드를 반복문으로 고쳐 쓴 식이다. 

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Main test = new Main();
    }

    public Main() {
        Scanner sc = new Scanner(System.in);
        int cnt = sc.nextInt();
        int M = sc.nextInt();

        int[] lumbers = new int[cnt];
        for (int i = 0; i < cnt; i++) {
            lumbers[i] = sc.nextInt();
        }
        //정렬
        Arrays.sort(lumbers);
        long start = 1;
        long end = lumbers[lumbers.length-1];
        long current_Max_H = 0;
        
        //범위를 유지하는 순간까지만
        while (start <= end){
            long H = (start+end)/2;

            long sum = sumCuttedLumbers(lumbers,H);

            if(sum < M){
                end = H -1;
            }else{
                //M이상을 만족하는 H중 가장 큰 값만 current_Max_H에 저장
                if(current_Max_H < H){
                    current_Max_H = H;
                }
                start = H+1;
            }

        }
        System.out.println(current_Max_H);


    }


    //output 해당 H로 잘랐을 때, 잘린 목재 길이의 합
    public long sumCuttedLumbers(int[] lumbers, long H) {
        long result = 0;
        for (int lumber : lumbers) {
            if (lumber - H < 0) {
                continue;
            }
            result += (lumber - H);
        }
        return result;
    }

}

 

 

 

결과

 

32778478 , 32777891 - 재귀 함수 이용 

32777797 - 반복문

 

재귀가 더 빨랐는데, 큰 차이는 없는 것으로 보인다.

 

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.