[백준 java] 1654 - 랜선자르기

1654번: 랜선 자르기

 

---

 

2512번 문제인 예산 문제와 같이 이진 탐색 알고리즘을 사용하였다

 

while문

제일 긴 랜선 길이(최대값)와 최소값 0을 더한 값에 2를 나누어 중심값을 구하고

K개의 랜선을 해당 중심값으로 나누고 (가진 랜선을 잘라 랜선만들기)

나눈 수를 더하여 만든 랜선의 수를 구한다. (가진 랜선으로 만들어진 랜선 수)

 

1. 해당 수가 M(만들어야 하는 랜선 수) 보다 작으면

중심값을 줄여 랜선 수를 더 만들어야 하므로 max = mid-1

2.  M(만들어야 하는 랜선 수)보다 크면

최적값을 찾기위해 최소값을 올려서 더 길게 랜선을 만들어본다 min = mid

 

이렇게 탐색 범위를 좁혀나가서 최적의 랜선값을 구한다

 

---

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

// 랜선자르기
// https://www.acmicpc.net/problem/1654
public class B1654 {
    static int N,M;
    static int[] intArr;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        intArr = new int[N];
        for (int i = 0; i < N; i++) {
            intArr[i] = Integer.parseInt(bf.readLine());
        }
        Arrays.sort(intArr);
        binarySearch();
    }

    private static void binarySearch() {
        long max = intArr[N-1];
        // 만약 intArr의 최대값이 1이라면 
        // (min+max)/2가 (0+1)/2 즉 0이 나올 수 있어서 
        // max의 최소값을 2로 만들어준다
        max++;
       
        long min = 0;
        while(max > min){
            long sum = 0;
            long mid = (min+max)/2;

            for(int i : intArr){
                sum += (i/mid);
            }
            if(sum < M){
                max = mid;
            }else{
            	//upper bound
           	//sum == M 일때 min을 옮겨준다
                min = mid+1;
            }
        }
        System.out.println(min-1);
    }
}