[BOJ] 2805번: 나무 자르기 (매개 변수 탐색)

1. 문제

2805번: 나무 자르기

(1) 정답의 최대치

• 정답의 범위: 0 ~ 10억 (Integer type)
• 잘린 나무의 길이 합 <= 나무 높이의 총합 = 100만 * 10억 (Integer 범위 초과 => long 타입 사용해야 한다.)

 

2. 접근

(1) 키워드 체크하기

• 적어도 M미터의 나무를 집에 가져가기 위해서 절다기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오

(2) 매개 변수 만들어 보기

• 정답을 "매개 변수(Parameter)"로 만들고 Yes/No 문제(결정 문제)로 바꿔 보기

• 모든 값에 대해서 Yes/No를 채웠다고 생각했을 때, 정렬된 상태인가? Yes

위와 같은 접근으로 매개변수 탐색 알고리즘을 사용해야 한다는 것을 알 수 있다.

매개변수 탐색 알고리즘이 모르고 있다면 아래 링크를 통해 공부해보는 것도 좋을 것 같다.

[Algorithm] 매개 변수 탐색 (Parametric Search)

 

3. 시간복잡도

• H를 정해서 결정 문제 한 번 풀기 => O(N)
• 정답의 범위를 이분 탐색하면서 풀기 => O(logX) 반복
• 총 시간 복잡도 : O(N logX)

 

4. 구현

• 이분 탐색 메서드 구현 (가능한 범위에서 H 탐색)
• 이분 탐색에서 선택된 H가 만족하는지 않는지 결정하는 satisfy 메소드 구현 

public class S3_2805 {
    static int N;
    static int M;
    static int[] tree;
    static int ans;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        String str = br.readLine();
        st = new StringTokenizer(str, " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        tree = new int[N+1];
        str = br.readLine();
        st = new StringTokenizer(str, " ");
        for (int i = 1; i <= N; i++) {
            tree[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(tree);
        binarySearch();
        System.out.println(ans);
    }

    static void binarySearch() {
        int L = 0;
        int R = 1000000000;
        ans = 0;

        while (L<=R) {
           int mid = (L+R)/2;
           if(satisfy(mid)) {
               ans = mid;
               L = mid + 1;
           } else {
               R = mid - 1;
           }
        }
    }

    static boolean satisfy(int h) {
        long sum = 0L;
        for (int i = 1; i <=N; i++) {
            if(tree[i] - h > 0) {
                sum += (tree[i] - h);
            }
        }
        return sum >= M;
    }
}