[Algorithm/Java] 백준 1654번 - 랜선 자르기

---

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

---

📌 문제

문제 유형

• 이분 탐색

문제 설명

오영식은 길이가 제각각인 K개의 랜선을 가지고 있고, 이 랜선을 잘라서 N개의 같은 길이의 랜선을 만들고자 한다. 만들 수 있는 랜선의 최대 길이를 구하라.

입출력 예시

• 입력

  4 11
  802
  743
  457
  539
  

• 출력

  200
  

🔍 문제 풀이

만들 수 있는 랜선의 최대 길이를 구하는 문제 → 탐색 범위가 정해져 있다.

1. 1부터 가장 긴 랜선 길이까지의 범위를 기준으로 이분 탐색을 수행한다.
2. 각 중간 값 mid를 랜선 길이로 정했을 때, 총 몇 개의 랜선을 만들 수 있는지 계산한다.
3. 만들 수 있는 랜선 개수가 n 이상이면 mid는 정답 후보가 되며, 더 긴 길이에서도 만들 수 있는지 확인한다.
4. 만들 수 있는 개수가 n 미만이면, mid는 너무 길기 때문에 더 짧게 자르기 위해 탐색 범위를 왼쪽으로 줄인다.

📌 놓친 점

low는 1로 설정한다

low = 0이면 line / mid에서 0으로 나눌 위험이 있음 → 런타임 에러

자르는 최소 단위는 1cm이므로 low = 1로 해줘야한다.

문제 조건 충족

조건을 만족하면 mid를 정답 후보로 저장하고, 더 큰 길이에서도 조건을 만족할 수 있는지 오른쪽 구간을 탐색해야 한다.

문제에서 “N개를 만들 수 없는 경우는 없다”고 명시되어 있으므로, 정확히 N개가 아니라 N개 이상을 만들 수 있으면 조건을 충족한 것으로 본다.

처음엔 정확히 N개를 만들어야 한다고 착각했다.

💻 전체 코드

package org.example;

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

public class Main {
    static int max_line, k, n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        k = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        int[] lines = new int[k];

        for(int i=0; i<k; i++){
            lines[i] = Integer.parseInt(br.readLine());
        }

        max_line = 0;
        for(int line:lines){
            if(line>max_line){
                max_line=line;
            }
        }
        binary(lines);
    }

    public static void binary(int[] lines) {
        long low = 1;
        long high = max_line;
        long result = 0;

        while (low <= high) {
            long mid = (low + high) / 2; // 현재 자를 길이 후보
            long cnt = 0;

            for (int line : lines) {
                cnt += line / mid; // mid 길이로 잘랐을 때 랜선 개수 누적
            }

            if (cnt >= n) { // 만들 수 있는 개수가 충분하면
                result = mid;      // 최대 길이 후보 저장
                low = mid + 1;     // 더 긴 길이도 가능한지 탐색
            }
            else {                 // 아니면
                high = mid - 1;    // 더 짧게 잘라야 함
            }
        }

        System.out.println(result);
    }