[백준 - 2805] 나무 자르기 - Java

문제 설명

 

2805번: 나무 자르기

 

풀이 회고

해당 문제는 이분 탐색을 이용하여 해결할 수 있었습니다. 우선 문제에서 요구하는 것은 최소 m 만큼의 나무 높이를 얻기 위해 n개의 나무를 자를 절단기의 최대 높이를 구하는 것입니다.

 

우선 이분 탐색을 위해 다음과 같이 n개의 나무의 높이를 배열 각각의 요소에 할당한 후 오름차순으로 정렬합니다.

 

        for (int i = 0; i < n; i++) {
            trees[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(trees);

 

이후 문제에서 요구하는 절단기의 높이를 구하기 위해 이분 탐색을 위한 시작점을 0으로, 끝점을 나무의 최대 높이로 지정합니다. 이때 절단기의 높이가 0이라는 것은 모든 나무를 다 베어 각각의 나무 높이 합 만큼의 나무 높이(sumOfCutTrees)를 얻을 수 있음을 의미하며, 절단기의 높이가 나무의 최대 높이라는 것은 모든 나무를 다 베지 못하여 0만큼의 나무 높이(sumOfCutTrees)만을 얻을 수 있음을 의미합니다.  이때 주의해야 할 점은 각각의 나무 높이가 최대 10억까지 될 수 있는데다가 나무의 개수가 최대 1백만개가 될 수 있으므로 sumOfCutTrees의 타입은 넉넉하게 long 타입으로 선언해주어야 합니다.

 

        long sumOfCutTrees;
        int start = 0, end = trees[n - 1], heightOfSaw;
        int result = 0;

        while (start <= end) {
            ...
        }

 

절단기의 높이를 시작점과 끝점을 기준으로 중간점으로 설정해가면서(이분 탐색을 하면서) 각각의 나무들을 베어가면서 얻을 수 있는 나무 높이를 구합니다. 이를 위해 별도 메서드 로직을 다음과 같이 구현해주었습니다.

 

    public static long getSumOfCutTrees(int heightOfSaw) {
        long sum = 0;

        for (int i = 0; i < n; i++) {
            if (trees[i] > heightOfSaw) {
                sum += trees[i] - heightOfSaw;
            }
        }

        return sum;
    }

 

이후 모든 나무를 베어 얻은 나무 높이가 목표로 하는 m 보다 작으면 끝점을 낮추어(절단기의 높이를 낮추어) 다음 탐색 시에는 더 많은 나무를 얻도록 하고 m 보다 크다면 시작점을 높여(절단기의 높이를 늘려) 다음 탐색 시에는 더 적은 나무를 얻도록 하여 문제에서 요구하는 값에 근접해지도록 합니다. 이때 모든 나무를 베어 얻은 나무 높이가 m 보다 같다면 이는 해당 절단기의 높이가 문제에서 요구하는 것처럼 최대의 높이를 가지기 때문에 더이상의 탐색이 필요 없이 while 문에서 break를 시킵니다.

 

        long sumOfCutTrees;
        int start = 0, end = trees[n - 1], heightOfSaw;
        int result = 0;

        while (start <= end) {
            heightOfSaw = (start + end) / 2;
            sumOfCutTrees = getSumOfCutTrees(heightOfSaw);

            if (sumOfCutTrees < m) {
                end = heightOfSaw - 1;
            }
            else if (sumOfCutTrees > m) {
                result = Math.max(heightOfSaw, result);
                start = heightOfSaw + 1;
            }
            else {
                result = heightOfSaw;
                break;
            }
        }

        System.out.println(result);

 

전체 소스 코드

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

class Main {

    static int[] trees;
    static int n, m;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        trees = new int[n];
        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            trees[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(trees);

        long sumOfCutTrees;
        int start = 0, end = trees[n - 1], heightOfSaw;
        int result = 0;

        while (start <= end) {
            heightOfSaw = (start + end) / 2;
            sumOfCutTrees = getSumOfCutTrees(heightOfSaw);

            if (sumOfCutTrees < m) {
                end = heightOfSaw - 1;
            }
            else if (sumOfCutTrees > m) {
                result = Math.max(heightOfSaw, result);
                start = heightOfSaw + 1;
            }
            else {
                result = heightOfSaw;
                break;
            }
        }

        System.out.println(result);
    }

    public static long getSumOfCutTrees(int heightOfSaw) {
        long sum = 0;

        for (int i = 0; i < n; i++) {
            if (trees[i] > heightOfSaw) {
                sum += trees[i] - heightOfSaw;
            }
        }

        return sum;
    }
}

 

 

참고자료

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