[Baekjoon] 1654: 랜선 자르기

문제

다양한 길이를 가진 n개의 랜선을 가지고 일정한 길이를 가진 k개의 랜선을 만들 때 만들 수 있는 최대 길이를 구하는 문제이다.

 

풀이

내 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Q1654 {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        String[] nk = br.readLine().split(" ");
        int n = Integer.parseInt(nk[0]);
        int k = Integer.parseInt(nk[1]);
        long[] lines = new long[n];
 
        long max = 0;
        for (int i = 0; i < n; i++) {
            lines[i] = Long.parseLong(br.readLine());
            max = Long.max(max, lines[i]);
        }
        
        // 이분 탐색
        // 랜선 개수는 중복으로 나올 수 있기 때문에 UpperBound로 접근 후 -1
        long left = 0;
        long right = max + 1;
        while (left < right) {
            long mid = (left + right) / 2;
 
            long count = 0; // 자른 랜선 개수
            for (long line : lines) {
                count += line / mid;
            }
            
            // 개수가 k보다 작으면 랜선을 길게 자른 것이므로 right 값 변경
            if (count < k) {
                right = mid;
                continue;
            }
            
            // 아니면 left 값 변경
            left = mid + 1;
        }
 
        System.out.println(right - 1);
    }
}

선형 탐색으로는 시간초과가 나기 때문에 이분 탐색으로 접근했다.

처음에 UpperBound / LowerBound 개념을 몰라서 헤메다가 결국 공부하고 다시 문제를 풀었다.

 

간단하게 기본 예제를 예를 들어 설명하면,

4 11
802
743
457
539

이 값에서 이분 탐색을 한다 하면, 1부터 803 사이의 값을 탐색한다.

즉 다음과 같이 803개의 배열에서 각 인덱스의 값은 랜선의 개수라고 생각하면 편리하다.

여기서 왜 802가 아닌 803을 right값으로 잡을까?

 

이유는, UpperBound이기 때문이다. UpperBound는 항상 원하는 값의 초과값을 가져다준다.

여기서 802를 right로 잡게될 경우, n과 k값이 1일 때 결과는 802여야 한다. 하지만 right는 절대 803이 될 수 없기 때문에 802 - 1인 801이 결과로 나오게 된다. 때문에 right를 나올 수 있는 최대 길이보다 +1 된 상태로 만들어 주어야 한다.

여기서 UpperBound로 값을 구하면 k+1의 첫번째 값, 즉 201을 구할 수 있다.

여기서 k의 최대길이 값은 구한 값에서 -1 이기 때문에 결괏값에 -1 을 하면 정답을 구할 수 있다.

 

회고

이분 탐색의 경곗값에 대한 개념과 right값 설정에서 많이 막힌 것 같다. 실버 문제라고 해서 만만하게 봤었지만 푸는데 좀 힘들었던 것 같다. 좀 더 기본을 단단히 다져야겠다.