boj 1654

이번엔 랜선 자르기 문제

랜선을 11개로 자리기 위해 최댓값을 구하는 문제이다

start 1 end 배열의 최대 +1 (803) 이 될것이다

그래서 mid를 구해서 현재 배열들을 나눈것들의 합이 m(11) 보다 작을시 (크기가 크다는뜻) end = mid 로 보낸다 근데 최댓값이니 upperbound 방식을 사용해야 한다

lowerbound upperbound 차이

/// lowerbound
if(target <= m){
 end = mid;
} // 가장 처음으로 와야함 
else{
	start = mid +1;
}
//upper bound
if(target < m){
 end = mid;
} // 가장 마지막으로 와야함 
else{
	start = mid +1;
}

전체 코드

private static StringBuilder sb = new StringBuilder();
    public static  void main(String[] args) throws  IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        long[] arr = new long[n];

        long start =1;
        long end = 0;
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(br.readLine());
            if(end < arr[i]){
                end = arr[i];
            }
        }

        end ++;
        while(start < end){
            long mid = (start + end) /2;

            long sum = 0;
            for(int i=0; i<n; i++){
                sum += (arr[i] / mid);
            }
            // 최대 랜선
            if(sum < m){
                end = mid;
            }else{
                start = mid +1;
            }
        }
        System.out.println(end-1);

    }