백준, 랜선 자르기(1654, java)

문제 설명

K개의 랜선이 있을 때 적당하게 잘라서 N개의 랜선으로 만들고 싶다. 이때 자르는 길이의 최댓값을 구하는 문제이다. 이때 자른 랜선의 길이가 N개보다 커도 된다. 즉, K개의 랜선을 자를 때 만들 수 있는 랜선이 N개 이상이 되는 최댓값을 구하면 된다.

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

1654번: 랜선 자르기

다만, 여기서 조심할 점이 굳이 K개의 랜선을 모두 자를 필요는 없다는 거다.

문제 풀이

첫 번째 접근

랜선의 길이를 기준으로 이분 탐색을 진행하면 되겠다고 생각했다. K개의 랜선을 모두 자를 필요는 없으니 왼쪽 값을 0, 오른쪽 값을 K개의 랜선 중 최댓값으로 넣어줬다.

 

그리고 이분 탐색을 진행하는데, check라는 함수를 따로 작성하여 mid로 K개의 랜선을 자를 때 얼마나 많은 랜선이 나오는지 확인해줬다. 이렇게 구한 랜선이 N보다 작을 때는 기준을 낮춰서 더 많은 랜선을 자르도록 했다. 그리고 크거나 같을 때는 upper bound를 사용할 것이기에 기준을 높여줬다.

 

여기서 크거나 같아 문제의 조건에 맞아 떨어지는데, 왜 탐색을 멈추지 않는지 궁금해 할 수도 있다.

 

그 이유는 바로 자르는 길이를 최대로 구해달라고 했기 때문이다. 예를 들어서 길이가 15인 랜선이 존재할 때 이를 총 3개로 나눈다고 생각해보자. 그렇다면 이때 가능한 길이는 4이거나 5일 것이다. 이때의 최댓값은 5이므로 답은 5가 될 것이다. 그러나 원하는 만큼의 랜선이 나오면 바로 탈출하다고 조건문을 작성하면 4가 나올 확률도 충분히 존재한다. 때문에 가능한 만큼 범위를 높여서 최댓값을 찾는 것이다.

 

또한 초기 값 중 right를 지정할 때 최댓값+1을 해줘야 한다. 

 

그 이유는 우리가 upper bound를 사용하고 있기 때문이다.  예를 들어서 left와 right가 같은 경우에 left < right가 아니기에 이분 탐색을 진행하지 않는다. 하지만 이렇게 되면 우리가 원하는 값은 left이지만 정답은 left-1이 되어 우리가 원하는 값이 나오지 않게 된다. 때문에 right+1을 해줘서 이러한 문제를 해결해주면 된다.

 

참고로 랜선의 최대 길이가 int 형의 최댓값에 근접하길래 대부분의 자료형을 long으로 작성했다.

코드

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.*;

public class Main {
    public static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input1 = br.readLine().split(" ");
        int K = Integer.parseInt(input1[0]);
        long N = Long.parseLong(input1[1]);
        long[] lens = new long[K];

        for(int i=0; i<K; i++){
            lens[i] = Long.parseLong(br.readLine());
        }

        long left = 0;
        Arrays.sort(lens);
        long right = lens[K-1];
        long mid = 0;

        while(left < right){
            mid = (left+right)/2;
            long sum = check(lens, mid);

            if(sum < N){
                //폭을 좁혀야 한다.
                //System.out.println("목표 보다 작으므로 자르는 길이를 낮춰야 한다.");
                right = mid;
            }else{
                //System.out.println("목표보다 같거나 크므로 자르는 길이를 높여야 한다.");
                left = mid+1;
            }
        }

        System.out.println(left-1);

    }

    public static long check(long[] lens, long length){

        long sum = 0;
        for(long len : lens){
            sum += (len/length);
        }

        return sum;
    }


}