질문
길이가 다른 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 설정이 막힌 부분이 많은 것 같습니다.
그는 돈 문제라고 말하자 침착해졌지만, 조금은 해결하기 어려운 것 같았다.
기본을 탄탄히 해야 합니다.