<Algorithm> 173. 나무자르기(BJO)

1. 2805번 나무자르기(BJO)

   사용 알고리즘 :  이분탐색

• 기준 설정까지는 괜찮았는데 답을 구하는 측면에서 나무 자른게 딱 떨어지지 않을때에 대한 처리가 미흡했다.

• 수학적으로 잘못접근해서 조금 오래걸렸다. 루프가 끝날때의 start인덱스를 출력했는데 그렇게 하면 결과조건을 충족하지 못했다.

• 최대의 높이니까 결과조건에 해당될때는 저장하고 그것을 출력하는 부분이 필요했다.

문제에 대한 접근&생각

1. 정답의 크기(나무높이)가 20000000 넘어감 -> 이분탐색!
2. 이분탐색으로 가장 최대의 높이를 찾아야함 -> 결과조건! (루프가 끝나는 순간이 아닌 최대에 도달한 값을 저장해야함)

내 코드 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

import java.util.Scanner;   public class Main {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int n = sc.nextInt();         int m = sc.nextInt();         int arr[] = new int[n];         int max = 0;         /****************************          * 높이를 기준으로 이분탐색을 하여          * 될수있는 경우 중 가장 최대 높이를          * 구하여 출력한다.          ****************************/         for(int i = 0; i < n ; i++) {             arr[i] = sc.nextInt();             max = Math.max(max, arr[i]);         }                  int start = 0;         int end = max;         int ans = 0;         while(start<end) {             int mid = (start+end)/2;             long total = 0;             for(int i = 0; i < n; i++) {                 total+= arr[i]-mid>0?arr[i]-mid:0;             }             if(total > m) {                 ans = mid;                 start = mid+1;             }else if(total < m){                 end = mid;             }else {                 ans = mid;                 break;             }         }         System.out.println(ans);     } }   Colored by Color Scripter

cs