백준[2805] java -나무자르기

이 문제에서 알아야할 점은 두가지이다.

 

1.이분탐색으로 풀 것

2.long타입 선언 

 

일단 문제를 보자 

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

 

이전에 공부했던 이분탐색을 생각해냈다.

특정한 값을 구해야할 때 그 시간을 줄여주는 좋은 방법이다.

 

이문제에서 long타입을 써야 하는 이유는 나무의 높이가 최대 1,000,000,000이기 때문이다

int형으로는 계산할 수가 없다.

import java.util.*;
import java.util.stream.Collectors;

public class Main {
   public static void main(String[] args)  {
       Scanner sc = new Scanner(System.in);

      int n= sc.nextInt();
      long height = sc.nextInt();

      long[] tree = new long[n];
      long max=0;
      for(int i=0;i<n;i++){
          tree[i]= sc.nextInt();
          if(i==0){
            max = tree[i];
            continue;
          }
           if(tree[i]>max)
              max= tree[i];
      }

      long start = 0;
      long last =max;

       while(start<=last){
          long mid = (start+last)/2;
          long result=0;

          for(int i=0;i<n;i++){
              if(tree[i]>mid) {
                  result += tree[i] - mid;
              }
          }

          if(result>=height){
              start = mid+1;
          }
          else{
              last = mid-1;

          }
      }
        System.out.println(last);



   }


}