[백준]JAVA - 1654번: 랜선 자르기

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

1654번: 랜선 자르기

풀이

이분 탐색을 이용해서 풀어야하는 문제이다.

잘 모르겠다면 아래의 포스팅을 먼저 보고 오는 걸 추천한다.

 

https://sookr5416.tistory.com/146

자바 이분 탐색 Arrays.binarySearch() 메서드 정의 및 사용 방법

예제를 보면서 문제를 살펴보겠다.

총 4개의 랜선을 가지고 동일한 최대 길이의 11개 랜선을 만들어야한다.

 

802, 743, 457, 539 길이의 랜선을 가지고 만들 수 있는 최대 길이는 200이다.

11개를 만들 수 있는 길이는 ···, 198, 199, 200 등이 있다. 그렇다면 최대값은 어떻게 뽑아낼 것인가?

 

완전 탐색으로 구할 수도 있겠지만 시간 초과가 발생할 것이다. 그렇기 때문에 이분 탐색을 이용해서 풀어볼 것인데 기존의 이분 탐색과 다르게 범위를 조금 변경해줘야한다. 기존 이분 탐색은 배열의 특정 인덱스를 가지고 했지만 이 문제에선 랜선의 길이를 범위로 해야한다.

 

문제에서 이미 가지고 있는 랜선의 길이는 최소 1cm부터 나온다고 적혀있다. 그렇다면 이분 탐색의 맨 왼쪽(low)값은 자동으로 1이 될 것이다. 오른쪽(high)값은 어떻게 될까? 단순하게 제공된 랜선의 최대 길이를 입력해주면 된다. 예제에서는 802가 될 것이다.

 

그렇다면 이제 이분 탐색을 돌리면 되는데 한 가지 생각할 것이 있다. 이 문제에서는 11개의 랜선을 만들 수 있는 길이가 많다. 그렇기 때문에 이분 탐색을 랜선 개수가 11개가 될 때 끝내는 게 아니라 끝까지 돌려줘야한다.

while (max >= min) {
    int cnt = 0;
    mid = (min + max) / 2;
            
    for (int i=0; i<arr.length; i++) {
        cnt += arr[i] / mid;
    }
            
    if (cnt < N) max = mid-1;
    else min = mid + 1;
}

 

<최종코드>

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int K = Integer.parseInt(st.nextToken()); // 필요한 랜선 개수
        int N = Integer.parseInt(st.nextToken()); // 이미 가지고 있는 랜선 개수
        
        int[] arr = new int[K];
        long max = 0;
        long min = 1;
        for (int i=0; i<arr.length; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            max = Math.max(max, arr[i]);
        }
       
        long mid = 0;
        while (max >= min) {
            int cnt = 0;
            mid = (min + max) / 2;
            
            for (int i=0; i<arr.length; i++) {
                cnt += arr[i] / mid;
            }
            
            if (cnt < N) max = mid-1;
            else min = mid + 1;
        }
        
        mid = (min + max) / 2;
        System.out.println(mid);
    }
}