백준 1654번 (랜선 자르기) 자바 Java

 

 

풀이 (참고)

1. 길이에서 최대값(max)은 주어진 랜선의 길이중 최대값+1로 설정하고 최소값(min)은 0으로 시작한다.
2. mid = (min+max)/2로 설정한 후 주어진 랜선의 길이에서 얻어낼 수 있는 랜선의 수 n을 구한다.
3. n과 N을 비교해 n<N이면 max = mid로 설정해 잘라지는 길이가 더 증가하도록 설정하고 아닌 경우 min = mid+1로 잘라지는 길이가 더 줄어들도록 설정한다.
4. 위의 과정을 min<max인 경우 반복한다.

주의할 점 데이터의 크기(잘랐을 때 구해지는 길이..)가 int의 범위를 넘을 수 있으므로 long으로 설정하고 실행한다.

 

 

import java.util.*;
import java.io.*;


public class Main {


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int K, N;
        StringTokenizer st = new StringTokenizer(br.readLine());
        K = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        int[] arr = new int[K];

        long max = 0;

        // 입력과 동시에 해당 랜선의 길이가 최댓값인지를 확인하고 max를 갱신
        for (int i = 0; i < K; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            if(max < arr[i]) {
                max = arr[i];
            }
        }


        // 반드시 max에서 +1 값이어야 한다.
        max++;

        long min = 0;
        long mid = 0;

        while (min < max) {

            // 범위 내에서 중간 길이를 구한다.
            mid = (max + min) / 2;


            long count = 0;

            // 구해진 중간 길이로 잘라서 총 몇 개가 만들어지는지를 구한다.

            for (int i = 0; i < arr.length; i++) {
                count += (arr[i] / mid);
            }

            /*
             *  [upper bound 형식]
             *
             *  mid길이로 잘랐을 때의 개수가 만들고자 하는 랜선의 개수보다 작다면
             *  자르고자 하는 길이를 줄이기 위해 최대 길이를 줄인다.
             *  그 외에는 자르고자 하는 길이를 늘려야 하므로 최소 길이를 늘린다.
             */
            if(count < N) {
                max = mid;
            }
            else {
                min = mid + 1;
            }


        }

        // UpperBound로 얻어진 값(min)에 -1이 최대 길이가 된다.
        System.out.println(min - 1);
    }
}