랜선 자르기 - 백준 BOJ 1654

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

1654번: 랜선 자르기

 

 

---

접근법

 

주어진 랜선들에 대해, 이 랜선들에서 동일한 L 이란 길이만큼의 랜선들을 잘라내어, 그 총 합이 N 을 만족하는지 확인하면 되는, 조건 자체는 간단한 문제이다

다만 랜선 최대의 길이가 2^31 - 1 점을 미루어 보아 브루트포스는 시간 초과가 난다

탐색 하는데 있어서 발생하는 시간을 줄이는건 이분탐색, 그 중에서도 대표적인 파라매틱 서치 문제의 유형이다

 

---

풀이 및 주의점

 

흔히 아는 이분탐색은 탐색의 범위가 주어지고, 그 중에서 특정한 값을 찾는 것이 목표이다

하지만 우리가 찾고자 하는 랜선의 최대 길이는 단순하게 나열된 랜선의 길이들 중 target 값을 찾는것이 아니다

랜선의 개수와, 각 랜선의 길이들이 주어질 때, 이들에게서 잘라낼 수 있는 동일한 길이의 랜선들의 개수가 N 을 만족할 때 그때의 동일한 랜선의 길이값들 중 최대를 찾는것

즉, 잘라낸 랜선이 가질 수 있는 길이의 범위를 설정하고, 이 범위들을 이분탐색 하면서 매 단계에서 주어진 길이만큼으로 랜선을 자를 때, 잘려진 랜선의 개수는 몇개가 나오는지를 확인해 나가면 된다

 

기존의 이분탐색에서는 현재 mid 값이 target 보다 작으면 범위의 최대를 줄이고, 반대의 case 에서는 범위의 최소를 늘려갔지만
동일한 길이로 주어진 랜선들을 모두 잘랐을 때, 이 때 랜선 조각들의 개수가 target 값과 어떻게 비교를 해야하는지 처음에는 잘 떠오르지 않았다.

이분탐색은 탐색 범위를 지속적으로 좁혀가는것이 핵심 이므로, 현재 탐색중인 길이로는 100 개의 랜선 조각이 나왔다고 했을 때, 내가 목표로 하는 랜선 조각의 개수는 100개보다 크다고 하면, 랜선 조각의 길이를 줄임으로서 랜선 조각의 개수를 늘릴수가 있다

이와 같은 방식으로 이분탐색을 수행해 조건을 만족하는 랜선의 길이중 최대를 리턴하면 된다

 

야심차게 풀이를 작성했다가 나처럼 틀린 사람이 있을텐데...

 

함정

 

이 구체적인 정보가 쉽게 함정에 빠지게 한다. 얼핏보면 int 값 이하구나~ 싶지만 이분탐색에 있어서 사용되는 모든 변수들을 int 로 처리하면 오버플로우가 날 수 있다. 어느 부분에서 오버플로우가 발생할지 다음 코드를 보며 예상해보자

 

static int bSearch(int left, int right, int[] lines, int targetLineCount) {
    if(left > right) {
        return 0;
    }

    int mid = (left + right) / 2;

    if(getMaxLineSegmentCountFromLines(lines, mid) >= targetLineCount) {
        return Math.max( mid, bSearch(mid + 1, right, lines, targetLineCount) );
    }

    return bSearch(left, mid - 1, lines, targetLineCount);
}

static int getMaxLineSegmentCountFromLines(int[] lines, int segmentSize) {
    int count = 0;

    for(int line : lines) {
        count += line / segmentSize;
    }

    return count;
}

 

처음에는 getMaxLineSegmentCountFromLines 에서 count 를 누산하면서 발생하는 줄 알고 해당 함수의 리턴값과 변수를 long 으로 수정했다 ( 실제로 segmentSize 가 1 인데 line 의 길이가 2^31 -1 로 여러개 있으면 발생 )

 

그래도 오버플로가 발생하는 듯 했고, 이는 mid 를 구하는 과정에서 발생함을 찾아냈다 ( [0, 2^31] -> [2^30, 2^31] 로 탐색하면 두번째에서 left + right 에서 오버플로 발생 )

 

해당 부분을 수정하고 통과했다

 

---

코드

 

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

public class Main {

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

        int[] tokens = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        int lineCount = tokens[0];
        long targetLineCount = tokens[1];

        int[] lines = new int[lineCount];
        int inputCount = 0;
        while(inputCount < lineCount) {
            lines[inputCount] = Integer.parseInt(br.readLine());
            inputCount++;
        }

        int maxLineSize = Arrays.stream(lines).max().getAsInt();

        System.out.println(
                bSearch(1, maxLineSize, lines, targetLineCount)
        );
    }

    static long bSearch(long left, long right, int[] lines, long targetLineCount) {

        if(left > right) {
            return 0;
        }

        long mid = (left + right) / 2;

        if(getLineSegmentCountFromLines(lines, mid) >= targetLineCount) {
            return Math.max( mid, bSearch(mid + 1, right, lines, targetLineCount) );
        }

        return bSearch(left, mid - 1, lines, targetLineCount);
    }

    static long getLineSegmentCountFromLines(int[] lines, long segmentSize) {
        long count = 0;

        for(int line : lines) {
            count += line / segmentSize;
        }

        return count;
    }
}