[백준] 2805번: 나무 자르기 (Java)

💡문제 분석 요약

나무의 수 N과 상근이가 집에 가져가려고 하는 나무의 길이 M, 나무들의 높이가 주어졌을 때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최대값을 구하는 문제이다.

• 시간 제한: 1초
• 메모리 제한: 256MB

 

💡알고리즘 설계

특정 조건을 만족하는 최댓값 구하기 ⇒ 이진탐색

• 탐색 범위
  • left: 가장 작은 나무 길이
  • right: 가장 높은 나무 길이
• 탐색 수행
  • mid: `left + (right - left) / 2`
  • 절단기에 mid를 설정했을 때 얻을 수 있는 나무 길이 구하기
• 범위 조정
  • 구한 나무 길이가 M보다 크거나 같으면 → 값을 더 높여야 함 → `left = mid + 1`
  • 구한 나무 길이가 M보다 작으면 → 값를 더 낮춰야 함 → `right = mid - 1`
• left가 right보다 작거나 같을 때까지 위 과정을 반복한다.
• right를 반환한다. (right는 항상 조건(M 이상의 나무를 얻을 수 있는)을 만족하는 최대 높이를 가리키기 때문)

 

💡코드

import java.io.*;
import java.util.*;

public class Main {
    static int N, M;
    static long[] trees;

    static void binarySearch() {
        long left = 0;
        long right = trees[N-1];
        long mid = 0;

        while(left <= right) {
            mid = left + (right - left) / 2;
            long sum = 0;
            for(long tree : trees) {
                if(tree > mid) sum += tree-mid;
            }
            if(sum >= (long)M) left = mid + 1;
            else right = mid - 1;
        }

        System.out.println(right);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);
        trees = new long[N];
        String[] treeInput = br.readLine().split(" ");
        for(int i=0; i<treeInput.length; i++) {
            trees[i] = Long.parseLong(treeInput[i]);
        }
        Arrays.sort(trees);
        binarySearch();
    }
}

 

💡시간복잡도

• 배열 정렬: $O(N log N)$
• 이진 탐색: 나무의 최대 높이가 H일 때, $O(log H * N)$

따라서 전체 시간복잡도는 $O(N log N + log H * N)$ 이다.

 

💡 틀린 이유

결과값을 mid로 설정했었다.

mid는 마지막 반복에서의 중간값으로, 루프 종료 시점에서 mid는 최신 상태가 아닐 수 있다.

예시: 나무 높이 [10, 15, 20], M = 15

마지막 두 번의 반복:

left = 7, right = 8, mid = 7
자른 나무 길이의 합 = 16 (조건 만족)
left = mid + 1 = 8

left = 8, right = 8, mid = 8
자른 나무 길이의 합 = 13 (조건 불만족)
right = mid - 1 = 7

루프 종료: mid = 8 (틀림)

mid(8)은 마지막 반복에서 조건을 만족하지 않는 값이다.

 

💡 틀린 부분 수정

결과값으로 right 를 반환한다.

위의 예시와 동일한 과정 후:

루프 종료: right = 7 (정답)

right(7)가 조건을 만족하는 최대 높이이다.

⇒ right는 항상 조건을 만족하는 최대값을 가리키지만, mid는 마지막 반복에서 조건을 만족하지 않는 값을 가리킨다.

 

💡 느낀점 or 기억할정보

이진 탐색은 어떤 식으로 구현해야 하는 지는 알았지만, 결과값으로 어떤 값을 반환해야 하는지 아직 감을 잡지 못했다. 루프 안의 값을 계속 프린트하며 결과값을 찾는 연습이 필요할 것 같다ㅜ