[백준 1654] 랜선 자르기

in STUDY / PS

이분 탐색을 활용한 백준 1654번 자바 풀이

📚 문제

🔗 문제 링크

백준 1654번: 랜선 자르기

📖 문제 설명

  • 랜선 K개를 가지고 있음
  • 랜선은 길이가 제각각
  • 랜선을 모두 N개의 같은 길이의 랜선으로 만들어야 함
  • 이때 만들 수 있는 최대 랜선의 길이를 구해야 함

🔍 입력 조건

  • 첫째 줄에 K, N이 주어짐 (1 ≤ K ≤ 10,000, 1 ≤ N ≤ 1,000,000)
  • 둘째 줄부터 K줄에 걸쳐 각 랜선의 길이가 주어짐
  • 랜선의 길이는 2^31-1보다 작거나 같은 자연수

🔍 출력 조건

  • N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력

🧩 문제 분류

  • 알고리즘: 이분 탐색
  • 자료구조: 배열
  • 난이도: Silver II

🚀 접근 방법

  1. 가능한 랜선의 길이 범위를 설정 (1 ~ 2^31 -1)
  2. 이분 탐색을 사용하여 최적의 길이를 찾음
  3. 각 길이로 잘랐을 때 만들어지는 랜선의 개수를 계산
  4. N개 이상 만들어지면 길이를 늘리고, N개 미만이면 길이를 줄임

💻 구현

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

public class Main {
    static int[] arr;
    static int N, K;
    static long answer = 0L;

    public static void binarySearch(long start, long end){
        while (start <= end) {
            long mid = (start + end) / 2;

            long count = 0L;
            for (int i = 0; i < arr.length; i++) {
                count += arr[i] / mid;
            }

            if (count < N) {
                end = mid - 1;
            }
            else{
                answer = mid;   // N개 이상으로 나눠지면 그 길이를 저장
                start = mid + 1;
            }
        }
    }

    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());

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

        binarySearch(1, Integer.MAX_VALUE);

        System.out.println(answer);
    }
}

⏱ 시간 복잡도

  • O(K log(max(lines)))
    • 이분 탐색: O(log(max(lines)))
    • 각 단계에서 모든 랜선 확인: O(K)

💾 공간 복잡도

  • O(K): 랜선의 길이를 저장하는 배열의 크기

🧪 테스트 케이스

입력출력
4 11
802
743
457
539		200

📝 회고

  • count 셀 때와, mid값을 구할 때, Integer 값을 넘어간다는 점을 고려했어야 했다.
  • N개보다 많이 만드는 것도 N개를 만드는 것에 포함한다. 라는 조건을 못 봐서 시간이 좀 걸림.

📚 참고 자료

없음