Q 2805 나무 자르기

💡 문제 요약 및 분석

상근이는 나무 M미터가 필요하다. 상근이의 절단기는 높이 H를 지정하면 그 높이만큼 가로로 나무를 자른다. 나무의 높이가 20, 15, 10, 17 일 때, 상근이가 높이를 15로 지정한다면 길이가 5, 2인 나무가 남아 상근이는 총 7미터의 나무를 들고 갈 것이다. 나무를 필요한 만큼만 가져가고자 할 때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하자.

💡 알고리즘 설계

✅ 핵심 아이디어 : 이분 탐색으로 풀 수 있다. 여러 개의 나무를 자른 합계 sum이 목표값 M에 가까워질때까지 0부터 최대값 사이의 중간값 mid 를 조정하면서 M을 만족시키는 높이를 찾으면 된다.

  1. 입력

    • 표준입력으로 int N, int M 저장한다.
    • 표준입력 받는 나무의 길이를 int[N] trees 배열에 저장한다. 이 때 주어지는 나무의 최대값 max 를 저장한다.

  2. 연산

    • left = 0, right = max
    • 중간값 mid를 계산한다. mid = (left + right) / 2
    • sum += trees[i] - mid 로 자른 나무의 합계를 저장한다.
    • 다음 경우의 수에 따라 중간값을 갱신한다. sum > M : left = mid + 1 sum < M : right = mid - 1 sum == M : result = mid

  3. 출력

    • result 변수를 출력한다.

💡 코드


public class Main {

    static int read() throws Exception {
        int c = 0, n = 0;
        while ((c = System.in.read()) > 47) n = (n << 3) + (n << 1) + (c & 15);
        return n;
    }

    public static void main(String[] args) throws Exception {
        int N = read();
        int M = read();
        int[] trees = new int[N];
        int max = 0;
        for (int i = 0; i < N; i++) {
            int input = read();
            trees[i] = input;
            max = Math.max(input, max);
        }

        int left = 0;
        int right = max;
        int result = 0;

        while (left <= right) {
            long sum = 0;
            int mid = (left + right) / 2;
            for (int i = 0; i < N; i++) {
                if (trees[i] >= mid) {
                    sum += trees[i] - mid;
                }
            }
            if (sum >= M) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        System.out.println(result);
    }

}

💡 틀린 부분 분석

  • sum 변수는 long 으로 선언해야 한다. 왜냐하면 나무의 최대 높이가 1,000,000,000미터이기 때문에 한 번 자를 때 sum에 담을 수 있는 최대 길이가 1,000,000,000일 것이고, 이것을 N번 반복한다 하면 int형에 담을 수 있는 21억이라는 범위를 넘게 된다.

  • result = mid; 의 조건문이 틀렸다. 처음에는 sum <= M 일 때의 중간값을 결과로 저장하게 했는데, 문제의 요구 조건을 다시 생각해보면 sum, 즉 자른 나무의 길이의 총합이 상근이가 원하는 길이 M보다 많아야 하기 때문에 sum >= M 일 때 중간값을 결과로 저장해야 한다.

💡 시간 복잡도, 공간 복잡도

시간 복잡도공간 복잡도
O(n * log max)O(n)