알고리즘 나무절단과 파라매트릭 서치

//나무를 입력받아서 절단기에 넣을수있는 최댓값을 이진 탐색을 사용하여 찾으라는 문제인것같다.
//처음에는 일단 배열에 나무 값을 전부 입력받고나서 Array.sort를 사용했다.
//근데 단순히 이작업을 하는데 먼저 입력 받는 반복문이 들어가고 추가로 정렬까지
//들어가는 바람에 속도가 엄청 저하됬다. (2배차이)
//그런데 이방식도 입력값이 엄청 많아지면 오히려 느려질수도
//처음에 중간값을 구할떄 min과 max를 /2를 했더니 소수점 자리가 버려져 계속해서 탐색이
//진행돼 +1을 해주었다.
public class Main {
    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 = Long.parseLong(st.nextToken());

        int[] trees = new int[n];
        st = new StringTokenizer(br.readLine());

        int min = 0;
        int max = 0;
        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(st.nextToken());
            trees[i] = num;

            if (max < num) {
                max = num;
            }
        }

        while (min < max) {
            int height = (min + max + 1) / 2;

            long result = 0;
            for (int tree : trees) {
                if (tree > height) { // 나무가 절단기의 높이보다 크면 자름.
                    result += tree - height;
                }
            }

            // 나무의 길이 합이 필요한 나무의 길이가 아닐때 이분 탐색중 범위 조정.
            if (result >= m) {
                min = height;
            } else {
                max = height - 1;
            }
        }

        System.out.println(min);

        br.close();
    }
}

파라메트릭 서치(Parametric Search)는 이분 탐색(Binary Search)의 한 종류로, 어떤 함수의 값을 최적화하는 문제를 해결하는 알고리즘이다. 이분 탐색과 유사한 방식을 사용하지만, 이분 탐색이 정렬된 배열에서 특정 값을 찾는 데 주로 사용되는 반면에, 파라메트릭 서치는 최적 값을 찾기 위해 이분 탐색을 사용한다.

파라메트릭 서치는 주어진 문제에 대한 최적의 값을 찾는 것을 목표로 합니다. 주로 최적화 문제에서 사용되며, 이분 탐색을 통해 최적 값을 찾아가는 과정을 거칩니다. 이를 위해 일반적으로 다음과 같은 단계를 거칩니다:

1. 이분 탐색 가능한 범위 설정: 최적 값을 찾기 위한 파라미터(매개변수)를 설정하고, 그 값의 범위를 정합니다. 이 범위는 대개 이분 탐색을 통해 조절.
2. 이분 탐색을 통한 최적 값 탐색: 이분 탐색을 사용하여 주어진 문제에 대한 최적 값을 탐색합니다. 이 때, 함수의 값을 비교하며 범위를 좁혀가며 최적 값을 찾는다.

반면에 이분 탐색은 주로 정렬된 배열에서 특정 값을 찾는 데 사용된다. 주어진 값이 배열에 존재하는지 여부를 확인하거나, 주어진 조건을 만족하는 가장 작은/큰 값을 찾는 등의 문제를 해결할 때 유용.

따라서 파라메트릭 서치는 최적화 문제를 해결하는 데 사용되며, 이분 탐색은 주로 정렬된 배열에서 값을 찾는 데 사용되는데 두 알고리즘은 서로 비슷한 개념을 사용하지만, 사용되는 상황과 목적이 다르다.