BOJ 1654 - 랜선 자르기

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

1654번: 랜선 자르기

 

• 길이가 제각각인 K개의 랜선 (1 <= K <= 1만)
• 랜선을 모두 N개의 같은 길이의 랜선으로 만들거임 ( 1 <= N <= 100만)
• 항상 K <= N
• 만들 수 있는 최대 랜선의 길이를 구하여라 (랜선의 길이는 2^31-1보다 작거나 같은 자연수 => int형)

 

아이디어

" 최대 "라는 키워드가 등장했으므로 이분 탐색을 먼저 고려해보았다.

 

 

원래 주어진 문제

• 원하는 랜선 개수 N을 얻을 수 있는 최대 랜선의 길이는 얼마인가?

 

이분 탐색을 위해 최대 랜선의 길이를 A 매개변수로 설정 후 문제를 뒤집어서 Yes or No 문제로 바꿔준다.

 

뒤집어서 만든 Yes or No 문제

• 어떤 랜선 길이 A로 잘랐을 때 원하는 랜선 개수 N개를 얻을 수 있는가? 

이분탐색을 실행해서 길이 A마다 Yes or No를 물어본 후 가장 마지막으로 대답된 Yes인 A 길이를 찾아낸다.

 

시간 복잡도

• Yes or No 문제를 한번 물어보는데 걸리는 시간은 O(K)이다. K개의 랜선 리스트를 돌면서 나눠 더해주기만 하면 되기 때문이다.
• 이분 탐색은 A의 범위가 1~2^31-1 즉, 1~Integer.MAX_VALUE 이기 때문에 최대 질문 횟수가 약 log 21억이기 때문에 시간 복잡도를 약 O(log 21억)을 가진다.
• 따라서 총 시간 복잡도는 O(K log 21억) 이라서 2초 안에 풀이가 가능하다. 

 

 

구현

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

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int K, N;
    static int[] lens;

    static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        // 길이가 제각각인 K개의 랜선
        K = Integer.parseInt(st.nextToken());

        // 원하는 랜선 개수 N
        N = Integer.parseInt(st.nextToken());

        lens = new int[K + 1];
        for (int i = 1; i <= K; i++) {
            lens[i] = Integer.parseInt(br.readLine());
        }
    }

    static void pro() throws IOException {
        long L = 1;
        long R = Integer.MAX_VALUE;
        long ans = 0;

        while (L <= R) {
            long mid = (L + R) / 2;

            if (YesOrNo(mid) == true) {
                L = mid + 1;
                ans = mid;
            } else {
                R = mid - 1;
            }
        }

        bw.write(ans+" ");
    }

    static boolean YesOrNo(long A) {
        // A 길이로 잘랐을 경우 N개 만큼의 랜선을 얻을 수 있는가? Yes or No?
        long sum = 0;

        for (int i = 1; i <= K; i++) {
            sum += lens[i] / A;
        }

        if (sum >= N) {
            return true;
        } else {
            return false;
        }
    }

    public static void main(String[] args) throws IOException {
        init();

        pro();

        bw.close();
    }

}