알고리즘 풀이(JAVA) - [이분 탐색] 백준 알고리즘-2805(나무 자르기)

By on October 10, 2019

문제

문제 링크 : 이분탐색-나무 자르기 https://www.acmicpc.net/problem/2805

이분탐색 나무 자르기 문제

풀이

  • 이 문제는 랜선자르기(https://parkhyeokjin.github.io/algorithm/2019/10/09/baekjoon-1654.html) 에서 고민을 많이 한 덕에 조금 쉽게 접근을 하였으나
    문제를 정확히 분석 하지 못한 탓에 수자례 실패를 맛봐야 했다.

    • 실수1. 상근이는 항상 나무를 가져갈 수 있다. 필요한 나무가 M 이지만 더 많이 가져 갈 수 있고 딱 맞게 가져갈 수도 있다.
      절단기를 최대한 크게 설정해서 나무를 최소한으로 자르는 것이 포인트.

  • 풀이 시작

    • 주어진 나무를 배열에 담는다. (int[] tree)
    • 이분 탐색할 범위는 0 ~ 가장 큰 나무의 길이 까지 설정 한다.
    • 조건 1. 나무를 잘라서 모두 더한 값이 상근이가 필요한 M 보다 크거나 같을 경우
      • 조건 1-1. 나무를 최소한으로 잘라야 하기 때문에 자른 나무의 총합(treeSum)을 비교하여 최소 값(minLen)을 저장한다.
    • 조건 2. 자른 나무의 총합(treeSum)이 상근이가 필요한 M 보다 작을 경우
      • 자른값이 M보다 작은경우는 너무 크게 잘랐을 경우 이므로 더 작게 자르기 위해 mid - 1을 하여 재탐색 한다.
    • 모든 탐색을 끝냈을 경우(left > right) 절단기를 최대한 설정 할 수 있는 maxCut 값을 반환한다.

소스

  • 나무 자르기(2805)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Baekjoon_2805 {
	
	private static int m = 0; //필요한 나무의 길이
	private static int[] tree;  //나무 배열
        private static long minLen = Integer.MAX_VALUE;  //자른 나무의 총합의 최소값을 저장 할 변수
	private static long maxCut = 0; //절단기의 톱날 높이 값
	
	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		String[] inputA = reader.readLine().split(" ");
		
		//나무의 수
		int n = Integer.parseInt(inputA[0]);
		//필요한 나무의 길이
		m = Integer.parseInt(inputA[1]);
		
		tree = new int[n];
		
		String[] inputTree = reader.readLine().split(" ");
		for (int i = 0; i < inputTree.length; i++) {
			tree[i] = Integer.parseInt(inputTree[i]);
		}
		Arrays.sort(tree);
		System.out.println(Bsearch(0, tree[tree.length - 1]));
	}
	
	public static long Bsearch(long left, long right) {
		long treeSum = 0;
		long mid = (left + right) / 2;
		if(left > right) return maxCut;
		for (int i : tree) {
			if(i < mid) continue; 
			treeSum += i - mid;
		}
		if(treeSum >= m) {
			if(treeSum <= minLen) {
				minLen = treeSum;
				maxCut = mid;
			}
			return Bsearch(mid + 1, right);
		}else {
			return Bsearch(left, mid - 1);
		}
	}
}

Back to blog