[JAVA] 백준 (실버2) 1654번 랜선 자르기

링크

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

---

입력 예제

4 11
802
743
457
539

---

출력 예제

200

---

풀이

문제에서 요구하는 랜선의 개수에 맞게 케이블을 잘라야 한다. 각 케이블을 자르는 길이로 나눈 개수를 모두 더한 값을 기준으로 이진 탐색을 진행한다.

우선 자르는 길이의 최솟값은 1, 최댓값은 가지고 있는 랜선 중 최댓값으로 설정한다.

long start = 1;
long end = Arrays.stream(cables)
        .max()
        .orElseThrow();

이제 최솟값이 최댓값보다 커지는 지점까지 이진 탐색을 진행한다. 잘린 랜선의 개수가 부족하면 더 작은 길이로 나눠야 하므로 왼쪽 데이터셋을 선택하고, 초과됐을 경우 더 길게 나눠야 하므로 오른쪽 데이터셋을 선택한다.

 s   e
  1 802 -> mid: 401, count: 5
  1 400 -> mid: 200, count: 11
201 400 -> mid: 300, count: 6
201 299 -> mid: 250, count: 8
201 249 -> mid: 225, count: 10
201 224 -> mid: 212, count: 10
201 211 -> mid: 206, count: 10
201 205 -> mid: 203, count: 10
201 202 -> mid: 201, count: 10
201 200 -> 탐색 완료

코드로 구현하면 다음과 같다.

while (start <= end) {
    long mid = (start + end) / 2;
    
    //잘린 랜선의 개수 카운트
    long count = 0;
    for (long cable : cables) {
        count += cable / mid;
    }
    
    if (count < N) {  //랜선이 부족할 경우
        end = mid - 1;
    } else {  //랜선이 초과될 경우
        start = mid + 1;
    }
}

전체 코드

//백준
public class Main {

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        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());  //필요한 랜선의 개수
        long[] cables = new long[K];

        for (int i = 0; i < K; i++) {
            cables[i] = Long.parseLong(br.readLine());
        }

        long start = 1;
        long end = Arrays.stream(cables)
                .max()
                .orElseThrow();

        while (start <= end) {
            long mid = (start + end) / 2;

            long count = 0;
            for (long cable : cables) {
                count += cable / mid;
            }

            if (count < N) {  //랜선이 부족할 경우
                end = mid - 1;
            } else {  //랜선이 초과될 경우
                start = mid + 1;
            }
        }

        System.out.println(start - 1);
    }
}