랜선 자르기란?
길이가 제각각인 랜선(케이블) 몇 가닥을 모두 같은 길이로 잘라 일정 개수(K개) 이상의 조각을 만들고 싶을 때, "한 조각의 최대 길이는 얼마인가?"를 구하는 문제입니다.
핵심은 정답(조각 길이) 자체를 이분탐색한다는 점입니다. 배열에서 값을 찾는 일반 이분탐색과 달리, "가능한 길이의 범위"를 절반씩 좁혀가며 답을 찾습니다. 이런 기법을 매개변수 탐색(Parametric Search) 이라고 부릅니다.
왜 이분탐색이 되나요?
조각 길이를 L이라 하면, 만들 수 있는 개수는 다음과 같습니다.
개수(L) = ⌊케이블₁ / L⌋ + ⌊케이블₂ / L⌋ + ... + ⌊케이블ₙ / L⌋- •L을 줄이면 개수는 절대 줄지 않습니다 → 단조성(monotonicity)
- •따라서 "개수 ≥ K"를 만족하는 L의 경계가 한 곳 존재합니다
- •그 경계를 이분탐색으로 찾으면 끝입니다
이 단조성이 매개변수 탐색의 전제 조건입니다. "최적화 문제(최대 길이는?)"를 "결정 문제(이 길이로 K개가 가능한가?)"로 바꾸는 것이 핵심 발상입니다.
동작 원리
1단계. 탐색 범위를 잡습니다. lo = 1, hi = 가장 긴 케이블 길이.
2단계. mid = (lo + hi) / 2 를 조각 길이 후보로 정합니다.
3단계. mid로 잘랐을 때 만들 수 있는 개수를 셉니다(결정 함수).
- •개수 ≥ K → 가능! 정답 후보로 저장하고
lo = mid + 1(더 길게 도전) - •개수 < K → 부족!
hi = mid - 1(더 짧게 잘라 더 많이)
4단계. lo > hi 가 될 때까지 반복하면, 마지막 후보가 정답입니다.
예제로 따라가기
케이블 [57, 42, 36, 20], 필요한 개수 K = 3 일 때:
| 조각 길이 L | 개수 계산 | 결과 |
|---|---|---|
| 29 | 1+1+1+0 = 3 | 가능 → lo=30 |
| 43 | 1+0+0+0 = 1 | 부족 → hi=42 |
| 36 | 1+1+1+0 = 3 | 가능 → lo=37 (정답 후보) |
| 39 | 1+1+0+0 = 2 | 부족 → hi=38 |
| 37 | 1+1+0+0 = 2 | 부족 → hi=36 |
lo(37) > hi(36) 이 되어 종료. 정답은 36 입니다. L=37이면 2개밖에 못 만들어 불가능했죠.
시간복잡도와 공간복잡도
| 복잡도 | |
|---|---|
| 시간 | O(N log L) |
| 공간 | O(1) |
조각 길이 후보를 log L 번 시도하고, 매번 N개의 케이블을 합산하므로 O(N log L) 입니다. 케이블 길이가 10억이라도 약 30번의 반복이면 충분합니다.
자주 하는 실수
- •lo를 0으로 시작: 길이 0으로는 나눌 수 없습니다. 반드시
lo = 1부터. - •개수 오버플로우: 케이블이 많고 길면 개수가 매우 커집니다. 64비트 정수(long)로 누적하세요.
- •경계 갱신 실수: "가능하면 더 길게(lo=mid+1)", "부족하면 더 짧게(hi=mid-1)" 방향을 헷갈리면 무한 루프나 오답이 납니다.
알고노트에서 직접 확인하세요
랜선 자르기에서 조각 길이가 매 단계 어떻게 좁혀지는지, 각 길이에서 몇 조각이 나오는지 알고노트 시각화로 단계별로 확인할 수 있습니다.