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

[문제 링크]

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

[난이도]

- Silver 2

 

[알고리즘]

- 파라메트릭 서치

- 이분탐색

 

[코드]

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] trees = new int[N];
        st = new StringTokenizer(br.readLine(), " ");
        int left = 0;
        int right = -1;
        for (int i = 0; i < N; i++) {
            trees[i] = Integer.parseInt(st.nextToken());
            right = Math.max(right, trees[i]); // 나무의 최대 높이 이상으로는 자를 수 없기때문에 최대값 구하기
        }

        while (left <= right) { // left가 right를 넘어서기 전까지 반복
            int mid = (left + right) / 2;
            long tree = 0; // 범위를 초과해서 long
            for (int i = 0; i < N; i++) {
                if (trees[i] > mid) {
                    tree += trees[i] - mid;
                }
            }
            if (tree >= M) { // 너무 많이 가져갔거나 정확히 가져갔을 경우
                left = mid + 1;
            } else if (tree < M) { // 너무 적게 가져갔을 경우
                right = mid - 1;
            }
        }
        System.out.println(right);
    }
}

[풀이]

• 이진 탐색 : 정렬된 일련의 값들이 주어졌을 때 그 값들 중에서 원하는 값을 찾는 알고리즘이. 
• 파라메트릭 서치 : 이진탐색과 다르게 주어진 일련의 값들이 아니라 주어진 범위 내에서 원하는 값 또는 원하는 조건에 가장 일치하는 값을 찾아내는 알고리즘.

이진 탐색은 값들이 주어지고 파라메트릭 서치는 범위가 주어진다.

이진탐색과 비슷하지만 약간 다르다. 솔직히 이해가 정확히 가지는 않는다. 

 

[참조한 글]

https://loosie.tistory.com/551