[99클럽 코테 스터디 2일차 TIL / 백준] 1654 - 랜선 자르기 (JAVA)

99클럽 코테스터디 2일차 TIL
KeyWord : BinarySearch, upper_bound, Parametric Search

문제

집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.

이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)

편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 $2^{31}-1$보다 작거나 같은 자연수이다.

출력

첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.

 

---

 

풀이

알고리즘 문제를 많이 접해보지 않았다면 어려웠을 법한 문제이다.

1cm부터 주어진 랜선의 최댓값 사이에서 조건을 만족하는 특정한 값을 찾아야 한다. 즉, 이진 탐색 문제이다. 이것을 확실하게 캐치하지 못했다면 애를 먹었을 확률이 높다.

이진 탐색을 살짝 변경하여, 탐색 종료 조건을 N개의 랜선을 만들 수 있을 때로 설정하면 된다.

하지만 일반적인 이진 탐색과는 살짝 다른데, 이 문제는 종료 조건이 하나가 되는 것이 아니라, 일정한 범위 내에 존재하는 모든 값이 종료 조건에 해당될 수 있기 때문이다.

문제의 예제 입력에서도 N개의 랜선을 만들 수 있는 랜선의 길이는 최댓값인 200cm 뿐만 아니라 여러 개가 존재한다. 199cm도 되고, 198cm도 되고 더 작은 수도 가능하다.

즉, 이진 탐색을 진행하다가 mid=198이 되어 탐색이 종료되는 경우가 생길 수 있다는 것이다. 우리는 이진탐색을 하면서도 해당하는 범위 내에서 최댓값을 찾을 수 있게끔 설계해야 한다.

https://st-lab.tistory.com/267

이렇게 값을 찾는 방법을 upper_bound라고 하는데, 관련하여 굉장히 설명이 잘된 글이라고 생각한다. 나도 이 글을 보고 공부했다.

여기까지 구현하였다면, 나머지는 그다지 어렵지 않다. 여기까지 구현한 후 막혔다면 아마 다른 조건에서 막혔을 법하다. (사실은 내가 헤맸던 부분들이다.)

private static long binarySearch(int[] cable, long max,int n) {  
    long min = 1;  
    max+=1;  
    while (min < max-1) {  
        long mid = (min + max) / 2;  

        int cnt = 0;  
        for (int i = 0; i < cable.length; i++) {  
            cnt += cable[i] / mid;  
        }  

        if (cnt >= n) {  
            min = mid;  
        } else if (cnt < n) {  
            max = mid;
        }
    }  
    return min;  
}

먼저 이해를 위해 이분탐색 코드를 살펴보고, 아래를 보는 것을 추천한다.

 

탐색 범위

괜히 시간복잡도 줄이겠다고 주어진 랜선 중 가장 작은 길이의 랜선을 max로 두고 이분탐색을 진행했다.

4 11
802
743
457
539

이 예제 입력을 기준으로 1~457 사이에서 찾은 것이다. 내 생각에 최소 길이인 457보다 큰 값이 들어가버린다면, 457cm의 랜선이 무시되어버리니, 정답이 나올 수 없다고 생각했다.

하지만,

3 3
10
10
1000

이렇게 입력이 들어오면 정답은 333이 된다. 즉, 다른 짧은 랜선을 활용하지 않더라도 다른 랜선의 길이가 충분히 길다면 해가 있을 수 있다.

 

오버플로우

오버플로우에 대해서는 다 아실 거라고 생각하므로 따로 설명하지는 않겠다. 모르신다면 검색하여 공부하고 오시길.

조건을 자세히 보면, 랜선의 최대 길이는 $2^{31}-1$라고 되어 있다. (나도 그랬지만) 대부분의 분들이 이것을 보고 아 그냥 int로도 풀 수 있는 문제구나, 했을 가능성이 있다. 입력 받고 출력할 때는 상관 없지만, 문제는 이진 탐색을 진행할 때 발생한다.

1 1
2147483647

2147483647는 $2^{31}-1$ 즉, int의 최댓값이다.

이렇게 값이 들어왔다고 가정하자. 당연히 위 예시에서의 해는 $2147483647$이다.

이럴 경우, $1$~$2147483647$ 사이의 범위에서 이진탐색을 진행할 것이다.

하지만 실제로는 $2147483647+1$을 max로 두고 탐색이 진행해야 한다. 일반적인 이분탐색이었다면 max 또한 탐색 범위에 포함되었겠지만, 여기에서는 min을 탐색값으로 설정하여 반환한다. 그렇기에 max 값이 탐색 범위에 포함되지 않는 문제가 발생하는 것이다.

이제 여기서 오버플로우가 발생한다.

$2147483647+1$은 $2^{31}$이다. 즉, int의 범위를 넘어가 오버플로우가 발생해버린다. 그렇기에 이분탐색을 진행하는 부분은 전부 long 자료형으로 진행해주어야 한다.

 

코드

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

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

        int k = Integer.valueOf(stk.nextToken());  
        int n = Integer.valueOf(stk.nextToken());  

        int[] cable = new int[k];  
        int max = 0;  
        for (int i = 0; i < k; i++) {  
            cable[i] = Integer.valueOf(br.readLine());  
            max = Math.max(max, cable[i]);  
        }  

        long ans = binarySearch(cable, max, n);  
        System.out.println(ans);  
    }  

    private static long binarySearch(int[] cable, long max,int n) {  
        long min = 1;  
        max+=1;  
        while (min < max-1) {  
            long mid = (min + max) / 2;  

            int cnt = 0;  
            for (int i = 0; i < cable.length; i++) {  
                cnt += cable[i] / mid;  
            }  

            if (cnt >= n) {  
                min = mid;  
            } else if (cnt < n) {  
                max = mid;
            }
        }  
        return min;  
    }  
}

 

References

https://st-lab.tistory.com/267