[PS] BOJ1654 랜선 자르기 ( BinarySearch ) with JAVA

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

1654번: 랜선 자르기

 

 

◎문제풀이

 

랜선K개를 동일한 길이의 랜선 N개 이상으로 만들 때, 최대 랜선의 길이를 구하는 문제이다. 

 

랜선 N개 이상으로 만드는 랜선의 길이는 1 ~ 랜선K개중 최대길이 사이에 존재한다. 범위 안에서 원하는 값을 탐색해야 하므로 범위를 반씩 줄일 수 있는 이분탐색을 사용해보자. 범위의 중간값으로 랜선K개를 나누었을 때 생성되는 랜선의 개수가 N개 이상이어야 한다. N개 이상이 되도록 만드는 중간값의 최대 길이를 구하는 것이 문제의 목적이다. 

 

 

mid에서 N개보다 크거나 같으면 [ mid+1  : end ] 범위를 찾아야 하고

mid에서 N개보다 작으면 [ start : mid-1 ] 범위를 찾아야 한다.

 

우리가 원하는 답은 크거나 같은 경우 중에서 최댓값을 구하는 것이다.  이분탐색 중 N개보다 크거나 같은 mid를 발견하면 mid는 크거나 같은 경우에 포함된 수를 의미한다. 그럼 계속 이분탐색하여 최댓값을 구해야 한다. 

 

 

 

이렇게 계속 이분탐색을 진행하면 mid가 최댓값에 도달한다. mid가 최댓값에 도달했음은 어떻게 알 수 있을까? 이분탐색에서 마자막 탐색은 더이상 이분할 수 없을 때이다. 

 

경우는 두 가지가 있다. 

 

1) 마지막 탐색에 최댓값이 갱신된 경우

 

마지막 탐색에 최댓값이 갱신되었다면 mid+1을 시도한다. mid+1이 end보다 작거나 같으면 이분할 수 있지만 end보다 크면 이분할 수 없다. 이는 즉 아래 그림을 의미한다. 

 

 

 

mid에 +1을 했을때 end가 작다는 의미는 mid와 end가 같음을 의미한다. 이는 더이상 이분할 수 없으니 현재 최댓값 mid가 정답이라는 의미이다.

 

2) 마지막 탬색에 최댓값이 갱신되지 않은 경우

 

 

 

 

 

마지막 탐색에서 최댓값이 갱싱되지 않으면 현재 mid는 최댓값이 아니고 이전 mid가 최댓값이 된다. 이분탐색 범위는 현재 mid에 -1을 하여 start에서 mid-1의 범위를 탐색해야 한다. 그러나 mid-1이 start보다 작으면 더이상 이분할 수 없다. 이는 start와 현재 mid가 같다는 의미이다. 현재 mid는 최댓값이 아니다. 이전 mid가 최댓값이다.

 

 

start가 현재 mid랑 같다는 의미는 이전 mid와 현재 mid가 붙어 있다는 의미이다. 좌측에 있는 이전mid는 크거나 같은 경우에 포함되어서 우측탐색을 시도한 mid이므로 현재 mid에서 -1을 한 값이 이전 mid이고 이 값이 최댓값이 된다.

 

 

결론은 start가 end보다 커질 때, end가 정답이라는 의미이다. 경우1에서 mid+1은 start이니 end가 정답이고 경우2도 mid-1이  end이고 end가 start보다 작으니 end가 정답이기 때문이다. 이를 코드를 통해 확인해보자. 

 

 

◎코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import static java.lang.Math.max;

//BOJ1654 랜선 자르기
public class Main {
    static int n;
    static int k;

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

        k = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        long[] lans = new long[k];
        long maxLan = 0;

        for(int i=0;i<k;i++){
            lans[i] = Long.parseLong(br.readLine());
            maxLan = max(maxLan, lans[i]);  //범위 설정을 위한 최대랜선길이
        }

        System.out.println(binarySearch(1, maxLan,lans)); // 이분탐색
    }

    public static long binarySearch(long start, long end, long[] lans){
        if( start > end ) return end; // start가 end보다 커지면 end 반환
        long mid = (start+end)/2; // 중간값 구하기
        if(getLineNum(mid,lans) >= n) return binarySearch(mid+1,end,lans); // 우측 구간 탐색하기
        else return binarySearch(start,mid-1,lans); // 좌측구간 탐색하기
    }
    
    // 생성 가능한 랜선의 개수 구하기
    public static int getLineNum(long line, long[] lans){
        int result = 0;
        for(long lan : lans){
            result += lan/line;
        }
        return result;
    }
}

 

 

정말 까다로운 문제였다. 이분탐색까지는 구현했으나 범위설정과 기저조건 설정이 너무 어려웠다... 다른 풀이를 봐도 이해가 안되어 고민을 많이 했던 문제였다.