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

✏️ 문제 탐색

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

 

N개의 나무를 절단해서 윗부분을 가지고 가려고 한다.

목재 절단기 높이를 최대 얼마로 정해야

적어도 M미터의 나무를 가져갈 수 있는지 구하는 문제이다.

✏️ 구현 아이디어

나무의 수는 최대 1,000,000개, 나무의 높이는 최대 1,000,000,000이므로 

브루트 포스를 사용하면 나무 높이가 K(1<=K<=10억)일 때 각각 나무의 수만큼 연산하게 되므로 시간 초과가 발생한다.

시간 복잡도가 적은 이진탐색을 사용하자.

 

4 7
20 15 10 17

이진 탐색으로 찾는 값은 목재 절단기의 높이 h

h는 최소 1, 최대 1,000,000,000이므로

start=1, end=1,000,000,000, mid=(1+1,000,000,000)/2

 

목재 절단기의 높이가 h일 때

가져갈 수 있는 나무의 길이 len가 M보다 크다면 -> h의 범위를 앞으로 조정해서 높이를 줄임

가져갈 수 있는 나무의 길이 len가 M보다 작다면 -> h의 범위를 뒤로 조정해서 높이를 늘림

 

✏️ 알고리즘

이진탐색

✏️ 시간 복잡도

나무의 높이를 이진 탐색할 때마다 나무의 수만큼 검사가 이루어지므로

시간복잡도는 O(log1,000,000,000*1,000,000)

약 9,000,000번의 연산이 발생한다.

따라서 제한 시간(1초) 안에 연산 가능하다.

✏️ 오답 노트

• 가져갈 수 있는 나무의 길이를 누적할 때 음수가 나오는 경우도 모두 더해서 틀림
  -> 양수만 길이로 누적해야 함
• 처음 탐색 범위를 지정할 때 start=trees[0], end=trees[N-1]으로 지정함
  -> 나무의 길이가 한 가지만 있는 경우 탐색 범위가 1로 한정지어짐

✏️ 코드 설계

1. 입력받기
2. 나무 높이를 저장할 배열 trees[], 목재 절단기의 높이를 저장할 변수 h 선언
3. 나무 높이 h를 이분탐색
   1. start=1, end=1,000,000,000, mid=(1+1,000,000,000)/2으로 시작
   2. start<=end인 경우 while문 실행
      1. 높이가 mid일 때 가져갈 수 있는 나무의 길이가 M보다 모자라면
         h를 줄여야 하므로 범위를 앞으로 조정
         end=mid-1
      2. 높이가 mid일 때 가져갈 수 있는 나무의 길이가 M보다 많으면
         h를 늘려야 하므로 범위를 뒤로 조정
         start=mid+1
      3. start-1 또는 end 반환
   3. 가져갈 수 있는 나무의 길이는 availableLength(h)로 구함 :
      각 trees[]값에서 절단기 높이 h를 뺀 값이 양수면 누적해서 구한다.

✏️ 정답 코드

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

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        //입력 받기
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        trees = new long[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            trees[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(trees);

        long start = 0;
        long end = 1000000000;

        while(start<=end){
            long mid = (start+end)/2;
            if(availableLength(mid) < M){
                //벤 목재가 M보다 모자라면 h를 줄인다.
                end = mid - 1;
            }else if(availableLength(mid) >= M) {
                //벤 목재가 M보다 많으면 h를 늘린다.
                start = mid + 1;
            }
        }
        System.out.println(end);

    }
    static long availableLength(long h){
        //절단기 높이를 h로 두고 나무를 자를 때
        //가져갈 수 있는 나무의 길이
        long length = 0;
        for(int i=0; i<N; i++){
            long val = trees[i]-h;
            if(val>0) length += val;
        }
        return length;
    }
}

✏️ Note

• 이분 탐색을 구현하는 게 익숙해졌다.
• 문제 분석한 것을 바탕으로 언제 범위를 앞으로, 뒤로 조정해야 하는지 혼자 구현할 수 있게 됐다.
• 이분 탐색 시 반환값을 무엇으로 지정해야 하는지 혼자 판단할 수 있게 되었다.
• 직접 start, end, mid를 가지고 시뮬레이션해보면서 정하면 된다.
• 1. 마지막 턴에 범위가 앞으로 조정되었다면 start=mid=end가 됨. 이 상태에서 구하고자하는 값은 start인지 end인지 start-1인지 등등.. 판단하기.
• 2. 마지막 턴에 범위가 뒤로 조정되었다면 ... 마찬가지로 판단해보기
• 마지막으로 탐색된 값을 리턴하려면 start=end일 때의 턴에 start, end 중에 뭐가 움직이느냐에 따라 달라짐.
• start가 움직이면 end를, end가 움직이면 start를 반환하면 된다.