B2805 나무자르기- 이진검색

B2805 나무자르기- 이진검색

이진 검색 이란? 뭘까요

선형 탐색을하게 되면 너무 많은 시간 복잡도를 사용하게 됩니다.

따라서 데이터를 둘로 나눠 찾고자하는값을을 탐색해가며 범위를 좁혀나가는것입니다.

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

2805번: 나무 자르기

문제 설명

• "B2805 나무 자르기"는 주어진 나무들을 일정 높이로 잘라서 필요한 총 나무 길이를 얻는 최대 절단 높이를 찾는 문제입니다.이 문제는 이진 탐색(binary search)을 사용하여 효율적으로 해결할 수 있습니다.
• 입력 설명: n 개의 나무와 필요한 총 나무 길이 m이 주어집니다. 각 나무의 높이는 배열로 입력됩니다.
• 목표: 주어진 나무들 중 일부를 일정 높이 이상으로 잘라내어, 잘라낸 나무 길이의 총합이 m에 가장 근접하도록 하는 최대 절단 높이를 찾는 것입니다.
• 절단 높이를 어떻게 결정할 것인가: 이진 탐색을 사용하여 가능한 절단 높이 범위를 좁혀나갑니다.
• 이진 탐색 과정:
  1. 절단 높이의 초기 범위를 설정합니다 (min은 0, max는 입력된 나무 높이 중 최대값).
  2. min과 max의 중간값 mid를 현재 절단 높이로 가정합니다.
  3. 모든 나무에 대해 mid 이상의 부분만 잘라서 총 길이를 계산합니다 (sum).
  4. sum이 목표 길이 m보다 작으면 max를 감소시키고, m보다 크거나 같으면 min을 증가시킵니다.
  5. min과 max가 교차할 때까지 반복합니다.

public class B2805 {
    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());
        int m = Integer.parseInt(st.nextToken());
        int max=0;
        int min=0;
        int [] trees= new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            trees[i] = Integer.parseInt(st.nextToken());
            max = Math.max(trees[i], max);
        }

//        Arrays.sort(trees); // 상관없음 붙이든말던

        while (min < max) {  //이분탐색들어감
            int mid = (max+min)/2;
            long sum =0;

            for (int treeH : trees) {
                if (treeH - mid > 0) {
                    sum+= treeH-mid;
                }
            }

            if (sum < m) {
                max = mid;
            } else {
                min = mid+1;
            }

        }
        System.out.println(min - 1);

    }
}
//
//4 11
//        802
//        743
//        457
//        539