(백준) 1654: 랜선 절단

질문


길이가 다른 n개의 LAN 케이블에서 k개의 고정 길이 LAN 케이블을 만들 때 최대 길이를 찾는 것이 문제입니다.

설명하다

내 솔루션

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 어레이의 각 인덱스 값은 다음과 같이 LAN 회선의 수라고 생각하면 편리합니다.

802 대신 803을 올바른 값으로 설정한 이유는 무엇입니까?

그 이유는 UpperBound이기 때문입니다.

UpperBound는 항상 원하는 값보다 큰 값을 반환합니다.

여기서 802를 오른쪽으로 취하면 n과 k의 값이 1일 때 결과는 802가 되어야 한다.

그러나 오른쪽은 803이 될 수 없으므로 결과는 801, 즉 802-1입니다.

따라서 정확하게 얻을 수 있는 최대 길이 +1 이상으로 할 필요가 있다.


여기서 UpperBound를 사용하여 값을 계산하면 k+1번째 값인 201을 얻을 수 있습니다.

여기서 k의 최대 길이 값은 결과값에서 -1이므로 결과값에 -1을 더하면 정답이 된다.

검토

바이너리 검색 경계값 개념과 rvalue 설정이 막힌 부분이 많은 것 같습니다.

그는 돈 문제라고 말하자 침착해졌지만, 조금은 해결하기 어려운 것 같았다.

기본을 탄탄히 해야 합니다.

error: Alert: Content selection is disabled!!