[백준] 1654번: 랜선 자르기 (Java)

💡문제 분석 요약

길이가 제각각인 K개의 랜선을 모두 같은 길이로 잘라 N개 이상의 랜선으로 만들 때, 만들 수 있는 최대 랜선의 길이를 구하는 문제이다. (나무 자르기 문제와 유사)

• 시간 제한: 2초
• 메모리 제한: 128MB

 

💡알고리즘 설계

만들 수 있는 최대 랜선의 길이를 구하기 ⇒ 이진 탐색

• 탐색 설정
  • left: 0
  • right: 랜선 길이 중 최대값
• 탐색 수행
  • mid: `left + (right - left) / 2`
  • mid 길이로 만들 수 있는 랜선 개수를 구한다. (`count`)
• 범위 조정
  • count가 N보다 크거가 같으면 → `left = mid + 1`
  • count가 N보다 작으면 → `right = mid - 1` (더 잘게 잘라야 함)
• left가 right보다 작거나 같은 동안 위 과정을 반복한다.
• 결과값으로 right를 반환한다.

 

💡코드

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

public class Main {
    static int K, N;
    static long[] lines;

    static void binarySearch() {
        long left = 0;
        long right = lines[K-1];

        while(left <= right) {
            long mid = left + (right - left) / 2;
            if(mid == 0) break;
            long count = 0;
            for(long line : lines) {
                if(line >= mid)
                    count += line / mid;
            }
            if(count >= N) left = mid + 1;
            else right = mid - 1;
        }

        System.out.println(right);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        K = Integer.parseInt(input[0]);
        N = Integer.parseInt(input[1]);
        lines = new long[K];
        for(int i=0; i<K; i++) {
            lines[i] = Long.parseLong(br.readLine());
        }
        Arrays.sort(lines);

        binarySearch();
    }
}

 

💡시간복잡도

• 배열 정렬: $O(K log K)$
• 이진 탐색: 랜선의 최대 길이를 H라고 할 때, $O(log H * K)$

따라서 전체 시간복잡도는 $O(K log K + log H * K)$

 

💡 틀린 이유

“런타임 에러 (/ by zero)” 발생: `java.lang.ArithmeticException`

나누기 0을 하면 발생하는 에러이다.

즉, mid가 0이면 오류가 발생하게 된다.

 

💡 틀린 부분 수정

mid가 0 이면 left와 right가 모두 0이라는 뜻이므로, mid가 0이면 루프를 종료하도록 조건을 추가했다.

수정 전

while(left <= right) {
    long mid = left + (right - left) / 2;
    long count = 0;
    for(long line : lines) {
        if(line >= mid)
            count += line / mid;
    }
    if(count >= N) left = mid + 1;
    else right = mid - 1;
}

 

수정 후

while(left <= right) {
    long mid = left + (right - left) / 2;
    if(mid == 0) break; // 조건 추가
    long count = 0;
    for(long line : lines) {
        if(line >= mid)
            count += line / mid;
    }
    if(count >= N) left = mid + 1;
    else right = mid - 1;
}

 

💡 느낀점 or 기억할정보

알고리즘은 이전에 풀이했던 “나무 자르기” 문제와 유사해서 금방 설계할 수 있었다.

한번에 맞힐 수 있을 줄 알았는데 mid가 0이 되는 경우 때문에 에러가 나서, 테스트 케이스에 대해 생각하는 것이 부족하다는 것을 느꼈다.