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

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

2805번: 나무 자르기

 

 

<문제 분석>
나무를 자르는데 총 N개의 나무를 높이 H로 잘라서 남은 길이의 합이 M이상이 되는 H의 최대값을 구하라.
  - N : 나무의 수 ( 1 <= N <= 1,000,000)
  - H : 자르는 나무의 높이
  - M : 필요한 나무 길이 ( 1 <= M <= 2,000,000,000)

M의 범위가 20억임. 이분탐색 아니면 타임아웃이 발생할 확률이 높음.

<풀이>
H의 최대값이니 UpperBound를 사용하자.
먼저 오름차순으로 높이를 정렬하고, UpperBound로 mid값을 구해서 자르고 남은 길이를 더하자.
원래 알고리즘은 길이가 M보다 작으면 start = mid + 1을 하고, M보다 같거나 크면 end = mid를 한다.
하지만 이 문제에서는 mid가 커질 수록 자르고 남은 나무의 길이는 작아지기 때문에 변형을 해야 한다.

    public int UpperBound(int min, int max, int key) {
        while (min < max) {
            int mid = (start+end)/2;
            // 자른 나무 길이의 합(CalTree(mid))이 M(key)보다 작다는 것은
            // 자르는 위치(H)가 높다는 의미이므로 높이는 낮춰야 한다.
            // 즉, 상한(max)값을 줄여야 한다.
            if (CalTree(mid) < key) {
                max = mid;
            // 자른 나무 길이의 합(CalTree(mid))이 M(key)보다 크다는 것은
            // 자르는 위치(H)가 낮다는 의미이므로 높이는 높여야 한다.
            // 즉, 하한(start)값을 줄여야 한다.
            } else { // key >= CalTree(mid)
                min = mid + 1;
            } 
        }
        return max;
    }

<수정점>
오름차순 정렬을 다시 할 필요없이 입력합수에서 최대값을 구하면 됨.
최소값은 0임.

 

<코드>

import java.util.Scanner;
import java.io.IOException;
import java.util.Arrays;
import java.lang.Math;

//[백준] 3055번 - 탈출 (Java)

public class Main {
    static int N, M, max=Integer.MIN_VALUE;
    static int A[];
    
	public void InputData() throws IOException
	{
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        A = new int[N];
        for (int i=0; i<N; i++) {
            A[i] = sc.nextInt();
            max = Math.max(max, A[i]);
        }
	}
    public long CalTree(int H) {
        long sum = 0;
        for (int x : A) {
            int res = x-H;
            if (res > 0) {
                sum += res;
            }
        }
        //System.out.println("CalTree("+H+")= "+sum);
        return sum;
    }

    public int UpperBound(int start, int end, int key) {
        while (start < end) {
            int mid = (start+end)/2;
            //System.out.println("s= "+start+", e= "+end);
            // mid를 증가시키면 CalTree(mid)는 감소
            if (CalTree(mid) < key) {
                //start = mid + 1; // mid값을 증가
                end = mid;
            } else { // key >= CalTree(mid)
                //end = mid; // mid값을 감소
                start = mid + 1;
            } 
        }
        return end;
    }
	public void Solve() {
        //Arrays.sort(A);
        int ans = UpperBound(0, max, M);
        System.out.println(ans-1);

	}
    
	public static void main(String[] args) throws IOException
	{
		Main m = new Main();
		m.InputData();///입력
		//코드를 작성하세요
        m.Solve();
	}
}