[백준 - 2805] 나무 자르기 .java

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

 

절단기 높이가 높을수록 가져갈 수 있는 나무가 적고 절단기 높이가 낮을수록 가져갈 수 있는 나무가 많아진다

 

 

• 톱의 높이를 정해서, 그보다 높은 나무만 잘림
• 잘린 나무들의 총합이 M 이상이 되도록 해야 함
• 가능한 톱의 높이 중 가장 큰 값을 출력 -> m이상일 때 최댓값으로 갱신

했는데 합할때의 값 타입을 int로 받았을 때 틀렸다

-> 잘린 길이 총합이 int 범위를 초과할 수 있음 (최대 10^15) 

=> long 타입으로 설정

 

cut < m 나무가 부족 → 톱을 더 낮춰야 함

cut >= m 충분 → 더 높여서 가능한 최대 높이를 찾기

이 부분만 어려웠다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

import java.util.StringTokenizer;

public class Solution {
	//나무를 x 높이로 잘랐을 때 잘려 나오는 총 나무 길이 계산 함수
	public static long findH(int[] trees, int x) {
		long hap =0;
		for(int i =0; i<trees.length;i++) {
			if(trees[i]>x) hap+=trees[i]-x;
		}
		return hap;
		
	}

    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	int n = Integer.parseInt(st.nextToken());
    	long m = Integer.parseInt(st.nextToken());//m은 long (최대 10^15까지 가능)
    	
    	st = new StringTokenizer(br.readLine());
    	
    	int[] trees = new int[n];
    	
    	for(int i=0;i<n;i++) {
    		int x = Integer.parseInt(st.nextToken());
    		trees[i] = x;
   
    	}
    	Arrays.sort(trees);
    	
    	int l = 0, r = trees[n-1];
    	int answer = 0;
    	while(l<=r) {
    		int mid = (l+r)/2;
    		//해당 높이로 잘랐을 때의 총 나무 길이
    		long cut = findH(trees,mid);
    		
    		//나무 부족 -> 더 잘라야함 => 톱 낮춰야
    		if(cut<m) r = mid-1;
    		else {
    			//나무 충분 -> 톱의 최댓값 갱신
    			answer = mid;
    			l = mid +1;
    		}
    		
    	}
    	System.out.print(answer);
    	
    
     }
    
}

 

 

 

다른 풀이

합만 구했던 나의 풀이와는 다르게 총합까지 한번에 확인해서 가능한지 여부를 반환하는 점이 다르다

import java.util.Scanner;

public class Solution {
    // 특정 절단 높이에서 가져갈 수 있는 나무 총합이 m 이상인지 확인
    public static boolean isPossible(int[] heights, int cut, int m) {
        long totalWood = 0;
        for (int h : heights) {
            if (h > cut) totalWood += h - cut;
        }
        return totalWood >= m;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(); // 나무 수
        int m = sc.nextInt(); // 필요한 나무 길이
        int[] trees = new int[n];

        int max = 0; // 가장 높은 나무 (탐색 상한 설정용)
        for (int i = 0; i < n; i++) {
            trees[i] = sc.nextInt();
            max = Math.max(max, trees[i]);
        }

        int l = 0, r = max, answer = -1;

        while (l <= r) {
            int mid = (l + r) / 2;
            if (isPossible(trees, mid, m)) {
                answer = mid;  // 가능한 높이 저장
                l = mid + 1;   // 더 높게 시도
            } else {
                r = mid - 1;   // 더 낮게 시도
            }
        }

        System.out.print(answer);
    }
}