백준[1654]-랜선자르기

이분 탐색 연습을 위해 푼 문제!

이분 탐색을 알기만 한다면 정말 쉬운 문제이다.

 

 

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

 

이분 탐색을 한두번밖에 경험해보지 않아서 아직 정확히 감은 오지 않는다.

아직까지의 생각은...

무언가 식을 세우는 것 보다 값을 하나하나 대입해서 답을 찾아야할 때 처음부터 다 찾으면 너무 많은 탐색을 해야하니 반으로 쪼개가며 탐색 횟수를 줄이는 방식인 것 같다.

 

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        long result =0;
        long need = sc.nextInt();
        long[] arr = new long[num];
        long sum =0;
        for(int i=0;i<num;i++){
            arr[i] = sc.nextInt();
            sum += arr[i];
        }

        //길이
        long first = 1;
        long last = sum/need;

        while(first <= last){
           long mid = (first+last)/2;
           int temp =0;
           for(int i=0;i<num;i++){
               temp+=arr[i]/mid;
           }
           //필요한 갯수보다 많이 잘린거(길이가 짧다)
           if(temp<need){
               last = mid-1;

           }else{//필요한 갯수보다 적게 잘린거(길이가 길다)
                first = mid+1;
               result = mid;

           }
        }

        System.out.println(result);

    }
}

 

long에 대한 안좋은 추억이 있다... 정말 코테에 대해서 1도 모를 때 무작정 구현했다가 문제를 못 푼적이 있다.

앞으로 long에 대해서 계속해서 상기하고 있어야 할 것 같다.

 

하지만 널리 알려진대로,자바에서는 int가 4바이트 long은 8바이트이므로 메모리에 문제가 되진 않는지 궁금하다

코테에는 이정도의 메모리는 문제가 되지 않는 걸까 🤔궁금쓰