링크

1654 랜선 자르기

문제

풀이

이 문제도 이분탐색으로 해결한다.
앞의 나무자르기와 같이 최대값을 찾는 문제로 end값을 출력하면 된다.
처음에 start값을 0으로 설정했는데 만약 테스트 케이스가
1 1
1
이 나온다면 start = 0, end = 1, mid = (start+end)/2이므로 mid가 0으로 나오고 0으로 나누기 때문에 Exception이 터진다. 그래서 초기값을 1로 설정해줘야 한다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

//1654 랜선자르기
public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = br.readLine().split(" ");

        int k = Integer.parseInt(arr[0]);
        int n = Integer.parseInt(arr[1]);

        List<Integer> list = new ArrayList<>();
        for(int i=0;i<k;i++){
            list.add(Integer.parseInt(br.readLine()));
        }

        Collections.sort(list);

        long start = 1;
        long end = list.get(list.size() - 1);

        //랜선의 최대길이(end)
        while(start <= end){
            long mid = (start + end) / 2;

            long sum = 0;
            for(int element : list){
                sum += element / mid;
            }

            if(sum >= n){
                start = mid + 1;
            } else{
                end = mid - 1;
            }

        }
        System.out.println(end);

    }

}