나무 자르기 ( 백준 2805 )

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

 

* 랜선 자르기와 똑같은 문제

* 랜선은 mid 값으로 나누었을때 갯수와 비교

* 나무는 mid 값으로 뺄셈을 했을때 길이와 비교하는것

* 로직은 비슷하지만 (mid+1)과 (mid-1)을 결정하는 decision() 함수를 구현할때 헷갈려서 글을 남긴다

 

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

public class BOJ2805 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int size = Integer.parseInt(st.nextToken());
        int length = Integer.parseInt(st.nextToken());
        int max = Integer.MIN_VALUE;
        int[] woods = new int[size];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < size; i++) {
            woods[i] = Integer.parseInt(st.nextToken());
            max = Math.max(max, woods[i]);
        }
        System.out.println(parametric(woods, max, length));
    }
    private static int parametric(int[] woods, int max, int length) {
        int left = 1, right = max, result = 0;
        while(left <= right) {
            int mid = (left+right)/2;
            // 더 잘라야함
            if(decision(woods, mid, length)) {
                result = mid;
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        return result;
    }
    private static boolean decision(int[] woods, int mid, int length) {
        long total = 0;
        for(int wood : woods) {
            if(wood-mid>=0) {
                total += wood-mid;
            }
        }
        return length <= total;
    }
}

 

* decions() 함수를 주목

* for() 반복문 안에 if() 조건을 확인하면 나무를 잘랐을때 모자르지 않을때를 분기를 걸었다

* 잘린 나무들을 total 변수에 할당

* for() 반복문이 끝났을때 목표 길이보다 더 많거나 같게 할당 받았을때 return 해줘야한다.

 - 이유는 GPT한테 물어보니  판단해야 할 기준은 “현재 높이 mid로 충분한 나무를 얻을 수 있는가?“이며, 이를 표현하는 올바른 방식이 total >= length이다.

* 따라서 더 많은 나무 길이를 할당 받았을때는 높이를 올려야 하므로 (left+1) 해줘야 함.

끝