[알고리즘] 백준 1654 랜선 자르기 - JAVA

www.acmicpc.net/problem/1654

1654번: 랜선 자르기

문제설명

K개의 랜선이 주어졌을 때, 각각의 랜선을 똑같은 길이로 잘라서 N개의 랜선을 만들어야한다.

 

이 때 랜선의 길이의 최대값을 출력하면 된다.

 

해결방법

랜선의 길이가 정수 최대값이기에 완탐으로 돌리면 안봐도 터질게 뻔하다.

 

그러므로 이분탐색을 통해 문제를 해결하였다.

 

이분탐색 내에서 left값은 케이블 길이의 최소값인 1이 될 것이고, right는 가장 긴 케이블을 고르면 된다.

 

만약 mid 만큼의 길이로 케이블을 자른다면 (i번째 케이블 / mid) 의 값이 자른 랜선의 개수가 된다.

 

만약 위의 값이 n보다 작다면, 케이블의 길이를 줄여야되므로 right = mid - 1을 해준다.

 

문제에서는 자른 랜선이 n의 개수보다 많더라도 n개를 자른 것으로 포함하기 때문에,

 

(i번째 케이블 / mid) 의 값이 n보다 크거나 같으면 저장되어 있는 최대값과 mid를 비교하여 더 큰 값을 최대값으로 저장한다.

 

그리고 left = mid + 1을 해준다 (케이블을 더 늘렸을 때 경우도 찾아보기 위해서)

 

간단한 소스코드기에 구현에 대한 설명은 필요없어보인다.

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class Main {

    static int k;
    static int n;
    static int cable[];
    static int sum;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s, " ");
        k = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        cable = new int[k];

        for (int i = 0; i < k; i++) {
            s = br.readLine();
            cable[i] = Integer.parseInt(s);
            sum += cable[i];
        }

        Arrays.sort(cable);
        System.out.println(binarySearch());
    }

    static long binarySearch() {
        long left = 1;
        long right = cable[k - 1];
        long result = 0;

        while (left <= right) {
            long mid = (left + right) / 2;
            long count = 0;

            for (int i = 0; i < k; i++) {
                count += cable[i] / mid;
            }

            if (count < n) {
                right = mid - 1;
            }
            else {
                result = Math.max(result, mid);
                left = mid + 1;
            }
        }
        return result;
    }
}