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

백준

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

스파게티 코더 2024. 8. 12. 22:04

문제

N 그루의 나무를 일정 길이로 자르고 남은 나무를 총 M 만큼 가져가야 할 때, 나무를 자르는 최대 길이를 구하는 문제.

아이디어

[JAVA] 백준 1654번: 랜선 자르기 (tistory.com) 이 문제와 동일하게 이분탐색으로 풀이를 진행하되, 자르고 남은 나무 길이가 필요하므로, 자르고 남은 값을 계산해주면 된다.
차이를 계산할 때, 음수를 더할 수도 있으므로 유의한다.

풀이

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        
        // 나무 길이를 입력받을 배열 선언
        long[] trees = new long[N];
        
        // 최소 길이를 1로 초기화
        long left = 1;
        long right = -1;

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            trees[i] = Integer.parseInt(st.nextToken());
            // 최대 길이 탐색
            right = Math.max(right, trees[i]);
        }

        while(right >= left) {
            // mid 계산
            long mid = (right+left)/2;
            
            // mid의 길이로 자르고 남은 나무 길이가 총 얼마인지 계산
            // 이때, 차가 양수일때만 체크
            long total = 0;
            for(long tree: trees) {
                if(tree-mid > 0) {
                    total += tree-mid;
                }
            }
            // 길이가 M 이상이면 left를 당겨 범위를 더 줄이고 반복
            if(total >= M) {
                left = mid + 1;
            }
            // 길이가 M 미만이면 더 짧아야 하므로 right를 당겨 범위를 더 줄이고 반복
            else {
                right = mid - 1;
            }
        }
        System.out.println(right);
    }
}

채점 결과

기타

또 N과 M의 범위를 못보고 오버플로우를 발생시켜 틀렸다... 이분탐색 문제에서는 꼭 유의하도록 해야겠다.

문제 링크

2805번: 나무 자르기 (acmicpc.net)