[Java] 백준 1654 랜선 자르기

 

 

문제

이미 가지고 있는 랜선의 개수 K와 만들어야 하는 랜선의 개수 N이 주어진다. 가지고 있는 랜선(길이가 제각각)을 잘라 동일한 길이의 랜선 N개를 만든다고 할 때, N개를 만들 수 있는 랜선의 최대 길이를 출력하는 문제.

 

- 1 <= K(이미 가지고 있는 개수) <= 10,000

- 1 <= N(만들어야 하는 개수) <= 1,000,000

- 1 <= wire(각 랜선의 길이) <= 2^31-1

 

이 때 주목할 점은 랜선의 범위가 1부터 2^31-1까지라는 것이다.

만약 선형탐색을 사용하여 N개를 만들 수 있는 랜선길이를 탐색한다면, 최대 2^31-1부터 하나씩 감소시켜가며 탐색해야 한다. 이 방식으로는 시간 제한 (2초)안에 풀이할 수 없다.

 

이와 같은 문제는 이진탐색을 사용하므로서 해결할 수 있다.

가능한 범위를 1/2로 줄여가며 탐색을 한다면 시간 제한안에 탐색을 완료할 수 있다.

 

 

주의할 점

1. 랜선길이는 자연수이므로, 이진탐색시 가장 작은 값 low는 1부터 시작해야한다.

[0으로 설정할 경우 반례] K(1) N(1) wire = {1}

- correct : 1

- wrong answer : 0

2. 이진탐색시 while문의 조건은 low <= high로 등호가 포함되어야 한다.

[low < high로 설정할 경우 반례] K(2) N(4) wire = {4,8}

- correct : 2

- wrong answer : 3

3. 변수의 타입을 조심해야 한다. int는 low, high, cnt의 모든 범위를 커버하지 못한다3

 

 

 

풀이

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

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[] wires = new int[K];
        long low = 1, high = 1; 
        for (int i = 0; i < K; i++) {
            wires[i] = Integer.parseInt(br.readLine());
            high = high < wires[i] ? wires[i] : high;
        }
//        Arrays.sort(wires); // 할 필요 없음

        while (low <= high) {
            long mid = (low + high) / 2;

            long cnt = 0;
            for (int i = 0; i < K; i++) {
                cnt += (wires[i]) / mid;
            }

            if (cnt >= N) { // mid 더 커도됨
                low = mid + 1;
            } else { // mid를 더 줄여야 됨
                high = mid - 1;
            }
        }

        System.out.println(high);    
    }
}

 

 

 

채점결과