[BOJ 1654] 랜선자르기 (java, 이진탐색)

 

 

---

문제 링크

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

1654번: 랜선 자르기

---

풀이

이진탐색 (매개변수 탐색) 풀이하면 되는 문제

 

문제 지문

K개 랜선이 있을때 필요한 랜선 N개를 만들기 위한 최대 랜선 길이 H를 구하시오.

 

뒤집은 지문 (매개변수 탐색*)

임의 길이 H로 랜선을 K개를 자를때, 필요한 랜선 N개를 만들 수 있는가? 이때 최대 랜선 길이 H는 얼마인가?

 

시간 복잡도

O(NlogN) 

 

최대값

랜선의 길이 최대값이 2^31 - 1 이기 때문에 integer 연산시 overflow 발생가능하므로 long 으로 처리해야 함

---

제출코드

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

public class BOJ1654 {
    static int K, N;
    static long[] lines;
    
    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        K = Integer.parseInt(st.nextToken()); // 이미 보유한 랜선 수
        N = Integer.parseInt(st.nextToken()); // 필요한 랜선 수

        lines = new long[K];
        for(int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            lines[i] = Long.parseLong(st.nextToken());
        }
    }

    static boolean isValidHeight(int H) {
        long total = 0;

        for(long l : lines) {
            long cnt = l / H;
            total += cnt;
        }

        return N <= total;
    }
    static void pro() {
        Arrays.sort(lines);

        long result = 0;
        long L = 0, R = Integer.MAX_VALUE;
        while(L <= R) {
            long height = (L + R) / 2;
            if(isValidHeight((int)height)) {
                L = height + 1;
                result = height;
            } else {
                R = height - 1;
            }
        }

        System.out.println(result);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
}