[백준] 2805. 나무 자르기(Java)

문제

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

 

풀이

해당 문제는 높이의 최댓값을 구하는 문제로 매개변수 탐색을 통해 해결했습니다.

매개변수 탐색으로 해결한 이유는 최댓값을 구하는 최적화 문제이며 이를 결정 문제로 해결하게되면 답을 도출하는 것이 수월하다고 생각했기 때문입니다.

 

방법은 다음과 같습니다.

1. 수열을 입력받으며 배열에 저장하고, 그 값들 중 최댓값을 저장합니다.

2. 매개변수 탐색을 하면서 문제에서 원하는 최댓값을 찾습니다.

1. s = 0, e = 입력값들 중 최댓값, while(e > s)
2. mid 값을 구해줍니다.(이때의 mid 값은 높이 입니다.)
3. mid(높이) 값을 기준으로 들고 갈 나무를 셉니다.(N과 높이의 값이 크기 때문에 long 타입으로 리턴해줍니다.)
4. c에서 구한 값 ≥ M(tgt)일 경우, ans에 저장하고 s = m+1해줍니다.
5. d 케이스가 아니라면, e = m으로 갱신해줍니다.
6. 매개변수 탐색이 끝나면 ans 값을 리턴합니다.

 

코드

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

public class Main {
    static int N;
    static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        arr = new int[N];

        st = new StringTokenizer(br.readLine());
        for(int i = 0 ; i < N ; i ++){
            int tmp = Integer.parseInt(st.nextToken());
            arr[i] = tmp;
            max = Math.max(max, tmp);
        }

        System.out.print(bs(0, max, M));
    }

    private static int bs(int s, int e, int tgt) {
        int m, ans = 0;

        while(e > s){
            m = (s + e) / 2;

            // m 일때의 결과 값
            long res = getResult(m);

            // 타겟값보다 크거나 같을 경우
            if(res >= tgt){
                s = m + 1;
                ans = m;
            }
            else e = m;
        }

        return ans;
    }

    private static long getResult(int m) {
        long sum = 0L;
        long cnt = 0;
        for(int i = 0 ; i < N ; i ++){
            if(arr[i] > m){
                sum += arr[i];
                cnt ++;
            }
        }

        return sum - (cnt * m);
    }
}